You are currently browsing the tag archive for the ‘spherical geometry’ tag.

Given three points {A,B,C} in the plane, the distances {|AB|, |BC|, |AC|} between them have to be non-negative and obey the triangle inequalities

\displaystyle  |AB| \leq |BC| + |AC|, |BC| \leq |AC| + |AB|, |AC| \leq |AB| + |BC|

but are otherwise unconstrained. But if one has four points {A,B,C,D} in the plane, then there is an additional constraint connecting the six distances {|AB|, |AC|, |AD|, |BC|, |BD|, |CD|} between them, coming from the Cayley-Menger determinant:

Proposition 1 (Cayley-Menger determinant) If {A,B,C,D} are four points in the plane, then the Cayley-Menger determinant

\displaystyle  \mathrm{det} \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & |AB|^2 & |AC|^2 & |AD|^2 \\ 1 & |AB|^2 & 0 & |BC|^2 & |BD|^2 \\ 1 & |AC|^2 & |BC|^2 & 0 & |CD|^2 \\ 1 & |AD|^2 & |BD|^2 & |CD|^2 & 0 \end{pmatrix} \ \ \ \ \ (1)

vanishes.

Proof: If we view {A,B,C,D} as vectors in {{\bf R}^2}, then we have the usual cosine rule {|AB|^2 = |A|^2 + |B|^2 - 2 A \cdot B}, and similarly for all the other distances. The {5 \times 5} matrix appearing in (1) can then be written as {M+M^T-2\tilde G}, where {M} is the matrix

\displaystyle  M := \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 1 & |A|^2 & |B|^2 & |C|^2 & |D|^2 \\ 1 & |A|^2 & |B|^2 & |C|^2 & |D|^2 \\ 1 & |A|^2 & |B|^2 & |C|^2 & |D|^2 \\ 1 & |A|^2 & |B|^2 & |C|^2 & |D|^2 \end{pmatrix}

and {\tilde G} is the (augmented) Gram matrix

\displaystyle  \tilde G := \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & A \cdot A & A \cdot B & A \cdot C & A \cdot D \\ 0 & B \cdot A & B \cdot B & B \cdot C & B \cdot D \\ 0 & C \cdot A & C \cdot B & C \cdot C & C \cdot D \\ 0 & D \cdot A & D \cdot B & D \cdot C & D \cdot D \end{pmatrix}.

The matrix {M} is a rank one matrix, and so {M^T} is also. The Gram matrix {\tilde G} factorises as {\tilde G = \tilde \Sigma \tilde \Sigma^T}, where {\tilde \Sigma} is the {5 \times 2} matrix with rows {0,A,B,C,D}, and thus has rank at most {2}. Therefore the matrix {M+M^T-2\tilde G} in (1) has rank at most {1+1+2=4}, and hence has determinant zero as claimed. \Box

For instance, if we know that {|AB|=|AC|=|DB|=|DC|=1} and {|BC|=\sqrt{2}}, then in order for {A,B,C,D} to be coplanar, the remaining distance {|AD|} has to obey the equation

\displaystyle  \mathrm{det} \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & |AD|^2 \\ 1 & 1 & 0 & 2 & 1 \\ 1 & 1 & 2 & 0 & 1 \\ 1 & |AD|^2 & 1 & 1 & 0 \end{pmatrix} = 0.

After some calculation the left-hand side simplifies to {-4 |AD|^4 + 8 |AD|^2}, so the non-negative quantity is constrained to equal either {0} or {\sqrt{2}}. The former happens when {A,B,C} form a unit right-angled triangle with right angle at {A} and {D=A}; the latter happens when {A,B,D,C} form the vertices of a unit square traversed in that order. Any other value for {|AD|} is not compatible with the hypothesis for {A,B,C,D} lying on a plane; hence the Cayley-Menger determinant can be used as a test for planarity.

Now suppose that we have four points {A,B,C,D} on a sphere {S_R} of radius {R}, with six distances {|AB|_R, |AC|_R, |AD|_R, |BC|_R, |BD|_R, |AD|_R} now measured as lengths of arcs on the sphere. There is a spherical analogue of the Cayley-Menger determinant:

Proposition 2 (Spherical Cayley-Menger determinant) If {A,B,C,D} are four points on a sphere {S_R} of radius {R} in {{\bf R}^3}, then the spherical Cayley-Menger determinant

\displaystyle  \mathrm{det} \begin{pmatrix} 1 & \cos \frac{|AB|_R}{R} & \cos \frac{|AC|_R}{R} & \cos \frac{|AD|_R}{R} \\ \cos \frac{|AB|_R}{R} & 1 & \cos \frac{|BC|_R}{R} & \cos \frac{|BD|_R}{R} \\ \cos \frac{|AC|_R}{R} & \cos \frac{|BC|_R}{R} & 1 & \cos \frac{|CD|_R}{R} \\ \cos \frac{|AD|_R}{R} & \cos \frac{|BD|_R}{R} & \cos \frac{|CD|_R}{R} & 1 \end{pmatrix} \ \ \ \ \ (2)

vanishes.

Proof: We can assume that the sphere {S_R} is centred at the origin of {{\bf R}^3}, and view {A,B,C,D} as vectors in {{\bf R}^3} of magnitude {R}. The angle subtended by {AB} from the origin is {|AB|_R/R}, so by the cosine rule we have

\displaystyle  A \cdot B = R^{2} \cos \frac{|AB|_R}{R}.

Similarly for all the other inner products. Thus the matrix in (2) can be written as {R^{-2} G}, where {G} is the Gram matrix

\displaystyle  G := \begin{pmatrix} A \cdot A & A \cdot B & A \cdot C & A \cdot D \\ B \cdot A & B \cdot B & B \cdot C & B \cdot D \\ C \cdot A & C \cdot B & C \cdot C & C \cdot D \\ D \cdot A & D \cdot B & D \cdot C & D \cdot D \end{pmatrix}.

We can factor {G = \Sigma \Sigma^T} where {\Sigma} is the {4 \times 3} matrix with rows {A,B,C,D}. Thus {R^{-2} G} has rank at most {3} and thus the determinant vanishes as required. \Box

Just as the Cayley-Menger determinant can be used to test for coplanarity, the spherical Cayley-Menger determinant can be used to test for lying on a sphere of radius {R}. For instance, if we know that {A,B,C,D} lie on {S_R} and {|AB|_R, |AC|_R, |BC|_R, |BD|_R, |CD|_R} are all equal to {\pi R/2}, then the above proposition gives

\displaystyle  \mathrm{det} \begin{pmatrix} 1 & 0 & 0 & \cos \frac{|AD|_R}{R} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \cos \frac{|AD|_R}{R} & 0 & 0 & 1 \end{pmatrix} = 0.

The left-hand side evaluates to {1 - \cos^2 \frac{|AD|_R}{R}}; as {|AD|_R} lies between {0} and {\pi R}, the only choices for this distance are then {0} and {\pi R}. The former happens for instance when {A} lies on the north pole {(R,0,0)}, {B = (0,R,0), C = (0,R,0)} are points on the equator with longitudes differing by 90 degrees, and {D=(R,0,0)} is also equal to the north pole; the latter occurs when {D=(-R,0,0)} is instead placed on the south pole.

The Cayley-Menger and spherical Cayley-Menger determinants look slightly different from each other, but one can transform the latter into something resembling the former by row and column operations. Indeed, the determinant (2) can be rewritten as

\displaystyle  \mathrm{det} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 - \cos \frac{|AB|_R}{R} & 1 - \cos \frac{|AC|_R}{R} & 1 - \cos \frac{|AD|_R}{R} \\ 1 & 1-\cos \frac{|AB|_R}{R} & 0 & 1-\cos \frac{|BC|_R}{R} & 1- \cos \frac{|BD|_R}{R} \\ 1 & 1-\cos \frac{|AC|_R}{R} & 1-\cos \frac{|BC|_R}{R} & 0 & 1-\cos \frac{|CD|_R}{R} \\ 1 & 1-\cos \frac{|AD|_R}{R} & 1-\cos \frac{|BD|_R}{R} & 1- \cos \frac{|CD|_R}{R} & 0 \end{pmatrix}

and by further row and column operations, this determinant vanishes if and only if the determinant

\displaystyle  \mathrm{det} \begin{pmatrix} \frac{1}{2R^2} & 1 & 1 & 1 & 1 \\ 1 & 0 & f_R(|AB|_R) & f_R(|AC|_R) & f_R(|AD|_R) \\ 1 & f_R(|AB|_R) & 0 & f_R(|BC|_R) & f_R(|BD|_R) \\ 1 & f_R(|AC|_R) & f_R(|BC|_R) & 0 & f_R(|CD|_R) \\ 1 & f_R(|AD|_R) & f_R(|BD|_R) & f_R(|CD|_R) & 0 \end{pmatrix} \ \ \ \ \ (3)

vanishes, where {f_R(x) := 2R^2 (1-\cos \frac{x}{R})}. In the limit {R \rightarrow \infty} (so that the curvature of the sphere {S_R} tends to zero), {|AB|_R} tends to {|AB|}, and by Taylor expansion {f_R(|AB|_R)} tends to {|AB|^2}; similarly for the other distances. Now we see that the planar Cayley-Menger determinant emerges as the limit of (3) as {R \rightarrow \infty}, as would be expected from the intuition that a plane is essentially a sphere of infinite radius.

In principle, one can now estimate the radius {R} of the Earth (assuming that it is either a sphere {S_R} or a flat plane {S_\infty}) if one is given the six distances {|AB|_R, |AC|_R, |AD|_R, |BC|_R, |BD|_R, |CD|_R} between four points {A,B,C,D} on the Earth. Of course, if one wishes to do so, one should have {A,B,C,D} rather far apart from each other, since otherwise it would be difficult to for instance distinguish the round Earth from a flat one. As an experiment, and just for fun, I wanted to see how accurate this would be with some real world data. I decided to take {A}, {B}, {C}, {D} be the cities of London, Los Angeles, Tokyo, and Dubai respectively. As an initial test, I used distances from this online flight calculator, measured in kilometers:

\displaystyle  |AB|_R = 8790

\displaystyle  |AC|_R = 9597 \mathrm{km}

\displaystyle  |AD|_R = 5488\mathrm{km}

\displaystyle  |BC|_R = 8849\mathrm{km}

\displaystyle  |BD|_R = 13435\mathrm{km}

\displaystyle  |CD|_R = 7957\mathrm{km}.

Given that the true radius of the earth was about {R_0 := 6371 \mathrm{km}} kilometers, I chose the change of variables {R = R_0/k} (so that {k=1} corresponds to the round Earth model with the commonly accepted value for the Earth’s radius, and {k=0} corresponds to the flat Earth), and obtained the following plot for (3):

In particular, the determinant does indeed come very close to vanishing when {k=1}, which is unsurprising since, as explained on the web site, the online flight calculator uses a model in which the Earth is an ellipsoid of radii close to {6371} km. There is another radius that would also be compatible with this data at {k\approx 1.3} (corresponding to an Earth of radius about {4900} km), but presumably one could rule out this as a spurious coincidence by experimenting with other quadruples of cities than the ones I selected. On the other hand, these distances are highly incompatible with the flat Earth model {k=0}; one could also see this with a piece of paper and a ruler by trying to lay down four points {A,B,C,D} on the paper with (an appropriately rescaled) version of the above distances (e.g., with {|AB| = 8.790 \mathrm{cm}}, {|AC| = 9.597 \mathrm{cm}}, etc.).

If instead one goes to the flight time calculator and uses flight travel times instead of distances, one now gets the following data (measured in hours):

\displaystyle  |AB|_R = 10\mathrm{h}\ 3\mathrm{m}

\displaystyle  |AC|_R = 11\mathrm{h}\ 49\mathrm{m}

\displaystyle  |AD|_R = 6\mathrm{h}\ 56\mathrm{m}

\displaystyle  |BC|_R = 10\mathrm{h}\ 56\mathrm{m}

\displaystyle  |BD|_R = 16\mathrm{h}\ 23\mathrm{m}

\displaystyle  |CD|_R = 9\mathrm{h}\ 52\mathrm{m}.

Assuming that planes travel at about {800} kilometers per hour, the true radius of the Earth should be about {R_1 := 8\mathrm{h}} of flight time. If one then uses the normalisation {R = R_1/k}, one obtains the following plot:

Not too surprisingly, this is basically a rescaled version of the previous plot, with vanishing near {k=1} and at {k=1.3}. (The website for the flight calculator does say it calculates short and long haul flight times slightly differently, which may be the cause of the slight discrepancies between this figure and the previous one.)

Of course, these two data sets are “cheating” since they come from a model which already presupposes what the radius of the Earth is. But one can input real world flight times between these four cities instead of the above idealised data. Here one runs into the issue that the flight time from {A} to {B} is not necessarily the same as that from {B} to {A} due to such factors as windspeed. For instance, I looked up the online flight time from Tokyo to Dubai to be 11 hours and 10 minutes, whereas the online flight time from Dubai to Tokyo was 9 hours and 50 minutes. The simplest thing to do here is take an arithmetic mean of the two times as a preliminary estimate for the flight time without windspeed factors, thus for instance the Tokyo-Dubai flight time would now be 10 hours and 30 minutes, and more generally

\displaystyle  |AB|_R = 10\mathrm{h}\ 47\mathrm{m}

\displaystyle  |AC|_R = 12\mathrm{h}\ 0\mathrm{m}

\displaystyle  |AD|_R = 7\mathrm{h}\ 17\mathrm{m}

\displaystyle  |BC|_R = 10\mathrm{h}\ 50\mathrm{m}

\displaystyle  |BD|_R = 15\mathrm{h}\ 55\mathrm{m}

\displaystyle  |CD|_R = 10\mathrm{h}\ 30\mathrm{m}.

This data is not too far off from the online calculator data, but it does distort the graph slightly (taking {R=8/k} as before):

Now one gets estimates for the radius of the Earth that are off by about a factor of {2} from the truth, although the {k=1} round Earth model still is twice as accurate as the flat Earth model {k=0}.

Given that windspeed should additively affect flight velocity rather than flight time, and the two are inversely proportional to each other, it is more natural to take a harmonic mean rather than an arithmetic mean. This gives the slightly different values

\displaystyle  |AB|_R = 10\mathrm{h}\ 51\mathrm{m}

\displaystyle  |AC|_R = 11\mathrm{h}\ 59\mathrm{m}

\displaystyle  |AD|_R = 7\mathrm{h}\ 16\mathrm{m}

\displaystyle  |BC|_R = 10\mathrm{h}\ 46\mathrm{m}

\displaystyle  |BD|_R = 15\mathrm{h}\ 54\mathrm{m}

\displaystyle  |CD|_R = 10\mathrm{h}\ 27\mathrm{m}

but one still gets essentially the same plot:

So the inaccuracies are presumably coming from some other source. (Note for instance that the true flight time from Tokyo to Dubai is about {6\%} greater than the calculator predicts, while the flight time from LA to Dubai is about {3\%} less; these sorts of errors seem to pile up in this calculation.) Nevertheless, it does seem that flight time data is (barely) enough to establish the roundness of the Earth and obtain a somewhat ballpark estimate for its radius. (I assume that the fit would be better if one could include some Southern Hemisphere cities such as Sydney or Santiago, but I was not able to find a good quadruple of widely spaced cities on both hemispheres for which there were direct flights between all six pairs.)

In a previous blog post, I discussed the recent result of Guth and Katz obtaining a near-optimal bound on the Erdos distance problem. One of the tools used in the proof (building upon the earlier work of Elekes and Sharir) was the observation that the incidence geometry of the Euclidean group {SE(2)} of rigid motions of the plane was almost identical to that of lines in the Euclidean space {{\bf R}^3}:

Proposition 1 One can identify a (Zariski-)dense portion of {SE(2)} with {{\bf R}^3}, in such a way that for any two points {A, B} in the plane {{\bf R}^2}, the set {l_{AB} := \{ R \in SE(2): RA = B \}} of rigid motions mapping {A} to {B} forms a line in {{\bf R}^3}.

Proof: A rigid motion is either a translation or a rotation, with the latter forming a Zariski-dense subset of {SE(2)}. Identify a rotation {R} in {SE(2)} by an angle {\theta} with {|\theta| < \pi} around a point {P} with the element {(P, \cot \frac{\theta}{2})} in {{\bf R}^3}. (Note that such rotations also form a Zariski-dense subset of {SE(2)}.) Elementary trigonometry then reveals that if {R} maps {A} to {B}, then {P} lies on the perpendicular bisector of {AB}, and depends in a linear fashion on {\cot \frac{\theta}{2}} (for fixed {A,B}). The claim follows. \Box

As seen from the proof, this proposition is an easy (though ad hoc) application of elementary trigonometry, but it was still puzzling to me why such a simple parameterisation of the incidence structure of {SE(2)} was possible. Certainly it was clear from general algebraic geometry considerations that some bounded-degree algebraic description was available, but why would the {l_{AB}} be expressible as lines and not as, say, quadratic or cubic curves?

In this post I would like to record some observations arising from discussions with Jordan Ellenberg, Jozsef Solymosi, and Josh Zahl which give a more conceptual (but less elementary) derivation of the above proposition that avoids the use of ad hoc coordinate transformations such as {R \mapsto (P, \cot\frac{\theta}{2})}. The starting point is to view the Euclidean plane {{\bf R}^2} as the scaling limit of the sphere {S^2} (a fact which is familiar to all of us through the geometry of the Earth), which makes the Euclidean group {SE(2)} a scaling limit of the rotation group {SO(3)}. The latter can then be lifted to a double cover, namely the spin group {Spin(3)}. This group has a natural interpretation as the unit quaternions, which is isometric to the unit sphere {S^3}. The analogue of the lines {l_{AB}} in this setting become great circles on this sphere; applying a projective transformation, one can map {S^3} to {{\bf R}^3} (or more precisely to the projective space {{\bf P}^3}), at whichi point the great circles become lines. This gives a proof of Proposition 1.

Details of the correspondence are provided below the fold. One by-product of this analysis, incidentally, is the observation that the Guth-Katz bound {g(N) \gg N / \log N} for the Erdos distance problem in the plane {{\bf R}^2}, immediately extends with almost no modification to the sphere {S^2} as well (i.e. any {N} points in {S^2} determine {\gg N/\log N} distances), as well as to the hyperbolic plane {H^2}.

Read the rest of this entry »

Archives