Abstract

Given n points on a sphere, how do you test whether they all lie in the same hemisphere? Not just north/south, east/west, but any hemisphere. This is equivalent to finding a plane through the origin so that all n points lie to one side of this plane. We give a deterministic algorithm with run time \(O(n^3)\).

Notes & Motivation

Since this problem was motivated by geography, we’ll be referring to earth’s surface and latitude, longitude measurements frequently. But this is a general problem in spherical geometry, and thus applies to star maps’ ascension/declination measurements. Also, we frequently normalize vectors to speak strictly about the unit sphere, but this is not necessary. One could pick n points in a cube centered at the origin and apply the exact same algorithm to find a plane through the origin lying to one side of all the points.

Also, there is quite a bit of literature that can be found to the effect of “Given n random points on a sphere, what is the probability they all lie in one hemisphere?” Yet, we never found in this largely algebraic literature a deterministic method for doing this test.

Definitions

Lemmas and Observations

  1. A Hemisphere can be uniquely defined by a Pole.
  2. Two Great Circles always intersect at exactly two antipodal points, unless they are the same Great Circle.
  3. A Hemisphere can be defined as all the set of all normalized vectors \(\vec{x} = (x,y,z)\) satisfying \(\vec{x} \cdot \vec{p} \ge 0\) for \(\vec{p}\) the Hemisphere’s Pole, or “the set of all points less than orthogonal” to the Pole.
  4. By (2), two Hemispheres always intersect at exactly two antipodal points, with two exceptions: (a) they are the same Hemisphere, in which case \(H_1 \cap H_2 = H_1 = H_2\), or (b) they share a Great Circle but their poles point opposite, in which case \(H_1 \cap H_2\) is just their shared Great Circle. (Example: the intersection of the Northern and Southern Hemispheres is the Equator)
  5. The intersection of two Hemispheres can be completely determined by the angle between their poles, \(\alpha = \cos^{-1}(\vec{p}_1 \cdot \vec{p}_2)\). If \(\alpha\) is zero, then they are the same Hemisphere. If \(\alpha\) is \(180^{\circ}\), then they are opposite Hemispheres. Anywhere in between, and the two Hemispheres intersect at exactly two antipodal points.
  6. These two antipodal points are given by \(\pm \vec{p}_1 \times \vec{p}_2\). However they must be normalized to continue working strictly on the unit sphere. If you think of them as infinite rays from the origin, then this is a loose requirement. For the sake of rigor, though, their exact definition must be \(\pm \frac{\vec{p}_1 \times \vec{p}_2}{|\vec{p}_1 \times \vec{p}_2|}\).

The Meat of the Argument

Imagine for a moment, we wanted to intersect three Hemispheres. The first and second (say, the Northern \(i\), with the Western \(-j\)) give a quarter of a sphere, a polygon with two edges, one running along the Equator, one up and over the North Pole. This section is the interior of this polygon, and every single point in the interior and on the boundary satisfy (3) for both hemispheres. Every single point is orthogonal or less than orthogonal to both the North Pole and the “West” Pole \((0^{\circ}, -90^{\circ})\).

Now suppose we are tossing in the third Hemisphere as well. There are three possibilities:
- The entire polygon is contained by the third Hemisphere. Ex: \(\vec{p} = (45^{\circ}, -90^{\circ})\)
- None of the polygon is contained by the third Hemisphere. Ex: \(\vec{p} = (-45^{\circ}, 90^{\circ})\). Note that the two antipodal points of the polygon are in this case, still included, but as n grows, the polygon shrinks, and this becomes a likely possibility.
- Part of the polygon is contained by the third Hemisphere, producing a new polygon with one extra edge and one extra vertex. Ex: \(\vec{p} = (0^{\circ}, 0^{\circ})\)

In any case, the polygon starts out as a Hemisphere (\(1\)-gon), then slowly gets chipped away as edges are added. As the polygon shrinks, it becomes more and more likely that the next Hemisphere addition won’t include any of the polygon at all. This means that no hemisphere can contain every point.

A very important note is that the way we are constructing this polygon makes it convex. Take any edge and extend it past its vertices and the entire polygon will lie to one side of this line, by definition. Regardless of how many \(n\) points are added, the resulting \(n\)-gon will be convex.

Interpretation of “The Polygon”

The resulting polygon’s interior consists of all the points that are less than orthogonal to every single starting point. Points along the edge are exactly orthogonal to exactly one starting point and less than orthogonal to the rest. The vertices are exactly orthogonal to exactly two starting points and less than orthogonal to the rest.

Therefore the polygon can best be interpreted as the set of all possible points through which a pole can be drawn defining a new Hemisphere containing every single starting point. If it is a large \(n\)-gon, then the starting points were probably clustered close together and the resulting polygon resembles a circle. If the “polygon” is a single point, then three or more starting points lie on the same Great Circle, and there is only one Hemisphere that can contain them all. If the “polygon” was reduced to nothing, then the points do not lie in the same Hemisphere, regardless of where the pole is placed.

The Algorithm

The key to converting this into an effective algorithm is taking the following as a theorem: The intersection of \(n\) Hemispheres takes the form of a polygon of degree \(\le n\) whose interior points represent every possible pole whose Hemisphere can contain all the starting points. Now, we can actually go through and very carefully construct this polygon by adding each point one at a time. But fortunately, we don’t have to.

Earlier, we observed that (6) two Hemispheres intersect at two antipodal points given by the positive and negative cross products of their poles. Since every vertex of the resulting polygon is the intersection of two Hemispheres, then every single vertex is either the positive or negative cross product of some pair of starting points.

For \(n\) points, there are \(n(n-1)\) pairs of points. Our polygon is a subset of these points, but which subset? Well, every vertex must be orthogonal or less than orthogonal to every starting point. So, (a) generate a list of every pairwise cross product and (b) check that cross product against every other starting point. If it is orthogonal or less than orthogonal to every single starting point, then it must be in the final polygon.

Is it an interior, edge, or vertex point? For our purposes, it doesn’t really matter. What matters is whether there are any or not. If there aren’t, then the answer to our big question is no, these \(n\) points do not lie in a hemisphere. If there are, then the answer is yes. A followup question might be how to define this hemisphere. Any of the resulting points will work. Because the figure is convex, you can even take the geometric center of these points and project them back on the unit sphere to get a “central” pole.