Library · The Fiddler: Solutions · Chapter 89

Can You Spin the Graph?

Revised Report an error

You graph y=∣x∣y=|x|, but it is rotated about the origin by a uniformly random angle in [0∘,360∘)[0^\circ,360^\circ). What is the probability the rotated graph still passes the vertical line test (still defines yy as a function of xx)?

The Fiddler, Zach Wissner-Gross, January 31, 2025(original post)

Solution

The graph is two rays from the origin, 90∘90^\circ apart, initially pointing at 45∘45^\circ and 135∘135^\circ. A pair of rays passes the vertical line test exactly when the two rays lie on opposite sides of the vertical axis: if both rays had a horizontal component of the same sign, a vertical line just past the origin would cross both. Writing the rays after rotation as aa and a+90∘a+90^\circ, we need cos⁡a\cos a and cos⁡(a+90∘)=−sin⁡a\cos(a+90^\circ)=-\sin a to have opposite signs, i.e. cos⁡asin⁡a>0\cos a\sin a>0, i.e. sin⁡2a>0\sin 2a>0. That holds for half of all aa, so P=12.P=\boxed{\tfrac12}.

The computation

Spin the actual graph: pick a random rotation, point both rays through it, and check whether their horizontal components disagree in sign (the vertical line test). The pass rate is one half.

import numpy as np
rng = np.random.default_rng(0)
phi = rng.uniform(0, 360, 2_000_000) * np.pi / 180
a, b = np.radians(45) + phi, np.radians(135) + phi
print((np.cos(a) * np.cos(b) < 0).mean())   # 0.5000

Extra Credit

In a more advanced course you sketch the 3D graph of z=∣x∣+∣y∣z = |x| + |y|, and a bout of dizziness rotates it randomly in space: the true zz-axis is equally likely to point towards any point of the unit sphere (and the xx-axis is then equally likely to point in any direction perpendicular to it). What is the probability that the result is still a function, with zz a function of xx and yy?

Solution

Being a function means passing the vertical line test: every line parallel to the new zz-axis meets the graph at most once. Only the direction uu of the new zz-axis matters, and it is uniform on the sphere.

The graph is the surface of the solid region K={z≥∣x∣+∣y∣}K = \{z \ge |x| + |y|\} above it, an upside-down square pyramid that goes on for ever. This region is a convex cone, and that is the key. Convex means that a line meets KK in a single stretch, possibly empty, possibly endless. Cone means that if KK contains a point pp, it also contains p+tup + tu for every t≥0t \ge 0 whenever the direction uu itself lies in KK.

If uu points into the cone. Take any line p+tup + tu that meets KK. Once on the line inside KK, moving further in direction uu never leaves it, so the stretch inside KK runs off to infinity in one direction. Going the other way, the line eventually leaves KK, and the graph is crossed exactly once. The same holds if −u-u points into the cone (the picture is simply upside down), and this is the case the main puzzle also counted: there, y=∣x∣y = |x| remained a function both right way up and upside down.

Otherwise. Take a line in direction uu through a point inside KK. Its stretch inside KK cannot run to infinity in either direction, because that would need uu or −u-u to point into the cone. So the stretch is bounded, the line enters and leaves, and it meets the graph twice. The test fails.

So the probability is the fraction of all directions lying in KK or in −K-K, which is 2Ω/(4π)2\Omega/(4\pi), where Ω\Omega is the solid angle of the cone. The cone’s edges point along (±1,0,1)(\pm1, 0, 1) and (0,±1,1)(0, \pm1, 1), and its axis (0,0,1)(0,0,1) splits it into four congruent spherical triangles with corners a=(0,0,1)a = (0,0,1), b=(1,0,1)/2b = (1,0,1)/\sqrt2, c=(0,1,1)/2c = (0,1,1)/\sqrt2. For a spherical triangle with unit corner vectors, the formula of Van Oosterom and Strackee gives tan⁡Ω△2=a⋅(b×c)1+a⋅b+b⋅c+c⋅a=1/21+12+12+12=13+22=3−22.\begin{aligned} \tan\frac{\Omega_{\triangle}}{2} &= \frac{a\cdot(b\times c)}{1 + a\cdot b + b\cdot c + c\cdot a} = \frac{1/2}{1 + \frac{1}{\sqrt2} + \frac12 + \frac{1}{\sqrt2}}\\ &= \frac{1}{3 + 2\sqrt2} = 3 - 2\sqrt2 . \end{aligned} So Ω=4Ω△=8arctan⁡(3−22)\Omega = 4\Omega_{\triangle} = 8\arctan(3 - 2\sqrt2), and  P  =  2Ω4π  =  4arctan⁡(3−22)π  ≈  0.2163 \boxed{\ P \;=\; \frac{2\Omega}{4\pi} \;=\; \frac{4\arctan\big(3 - 2\sqrt2\big)}{\pi} \;\approx\; 0.2163 \ } (The official extra-credit value is paywalled; this is my own.)

The computation

The check performs the vertical line test itself instead of using the cone argument. For each random direction of the new zz-axis it takes eight lines in that direction, through points chosen at random inside the region above the graph (any line that meets the graph twice must pass through that region), and counts how often each line crosses the surface. Along a line, the height above the surface is a straight-line function of the position except where xx or yy changes sign, so its zeros can be counted exactly from its values at those two points and far out at each end. A direction passes if no test line crosses more than once.

import numpy as np
rng = np.random.default_rng(1)

def crossings(p, u, T=1e6):
    """Number of times the line p + t*u meets the surface z = |x| + |y|."""
    g = lambda t: (p[..., 2] + t*u[..., 2]) - np.abs(p[..., 0] + t*u[..., 0]) \
                  - np.abs(p[..., 1] + t*u[..., 1])
    # g is linear between the parameters where x or y changes sign
    t1 = -p[..., 0]/u[..., 0]; t2 = -p[..., 1]/u[..., 1]
    ts = np.sort(np.stack([np.full_like(t1, -T), t1, t2, np.full_like(t1, T)]), axis=0)
    ts = np.clip(ts, -T, T)
    vals = np.stack([g(t) for t in ts])
    return (np.sign(vals[1:]) != np.sign(vals[:-1])).sum(axis=0)

def inside_points(n):
    """Random points strictly inside the region above the graph, below z = 2."""
    pts = []
    while len(pts) < n:
        q = rng.uniform([-2, -2, 0], [2, 2, 2])
        if q[2] > abs(q[0]) + abs(q[1]): pts.append(q)
    return np.array(pts)

N, K = 200_000, 8
u = rng.normal(size=(N, 3)); u /= np.linalg.norm(u, axis=1, keepdims=True)
P = inside_points(K)
worst = np.zeros(N, int)
for p in P:                                   # K test lines per rotation
    worst = np.maximum(worst, crossings(np.broadcast_to(p, (N, 3)), u))
ok = worst <= 1
print("still a function: %.4f +- %.4f" % (ok.mean(), np.sqrt(ok.mean()*(1-ok.mean())/N)))

It prints

still a function: 0.2173 +- 0.0009

within about one standard error of the boxed 0.21630.2163. (Eight test lines can very occasionally miss a failure close to the cone’s edge, which can only push the estimate up.)

Report an error on this page

Reports are stored by Netlify. See the privacy note.