4
$\begingroup$
  1. We draw n points, A, B, C, ... Z, on the upper hemisphere of a sphere, and their n antipodal points on the lower hemisphere, a, b, c, ..., z.

  2. We draw the n(n-1)/2 great circles connecting each pair of points on the upper hemisphere, noting that every great circle through X also passes through x.

  3. We now slice the sphere into two hemispheres by drawing an arbitrary great circle that does not pass through any of our points

  4. Each hemisphere must contain exactly one member from each of the sets {A, a}, {B, b}, {C, c}, ..., {Z, z}. We identify each hemisphere by the points it contains (something like AbcDEF); distances between the points are irrelevant.

The question is, How many distinct hemispheres are possible for any given initial configuration of n points? The answer appears to be n(n-1)+2, but I can't prove it.

$\endgroup$
1
$\begingroup$

Pairs of antipodal points on the sphere and great circles are dual: each pair of antipodal points defines a great circle perpendicular to those points and vice versa. The inadmissible great circles are exactly those that are given by an antipodal pair that is located on the dual great circle of any of the given $n$ pairs. This turns the problem into a "cut the cake" problem: Each distinctly labeled hemisphere is represented by a connected component in the complement of $n$ great circles.

Suppose that the $n$ given pairs are in general position. The first great circle divides the sphere into two connected components. For $m > 1$ adding the $m^{\textrm{th}}$ great circle adds $2m-2$ components. For $n$ great circles this gives a total of $2 + 2 + 4 + \dotsc + 2(n-1) = n(n-1) + 2$ connected components.

If the pairs are not in general position then the number of distinct hemispheres can be much lower. For example, consider the case that all pairs are themselves located on a single great circle.

$\endgroup$
1
$\begingroup$

The problem is equivalent to the following: given $N$ points over the upper hemisphere, how many subsets there are that are linearly separable from its complement? (where "linearly separable" here means separable by a great circle, or equivalently, by a plane that passes through the center of the sphere). By geometric considerations (for example, by a stereographic projection over an horizontal plane), the problem is equivalent to counting the linear dichotomies of $N$ points over a plane.

Then, let $S_N$ be the number of such dichotomies. Assume that the points are in "general position" (no three points are colinear). Consider what happens when a new point $P$ is added. Of the previous $S_N$ dychotomies, some number $S_N^P$ will be attainable by a line that passes over the new point $P$. In those cases, we have two new dichotomies for each old one (the new point can be on either set); in the complement, ($S_N-S_N^P$ cases) the new point doesn't add anything. Then

$$S_{N+1}=2 S_N^P + (S_N - S_N^P) = S_N^P + S_N$$

But $S_N^P$ can be obtained by considering the succesive lines that passes through it: there are $2 N$ such dichotomies.

Hence $$S_{N+1} = S_N + 2 N$$

which, together with the initial condition $S_1 =2$ gives

$$S_{N}= N(N-1)+2$$

(Adapted from here)

$\endgroup$
0
$\begingroup$

EDIT: As a comment pointed out, I was oversimplifying the problem. The solution as written is incorrect. I am leaving this here on the off-chance that my partial work is useful.


For an arbitrary configuration of $n$ top-points (which I'll denote $X_1,X_2,...,X_n$) and $n$ bottom points (which I'll denote $x_1,x_2,...,x_n$), we can say that there is one and only one hemisphere that contains a particular choice of $x_j$ or $X_j$ for each $j$. Thus, we are making a choice between 2 options $n$ times, which means there must be a total of $2^n$ possible distinct hemispheres.

Unless I have misunderstood the question, it would appear that the answer is $2^n$ rather than $n(n-1)+2$.


Another way to think of this: For each hemisphere on $n-1$ points, we can append either $X_n$ or $x_n$. Thus, every point added doubles the number of possible hemispheres. For $n=1$, there is only one possible choice of hemisphere.

$\endgroup$
  • $\begingroup$ "there is one and only one hemisphere that contains a particular choice" I don't think so. That would imply that any subset of $X_n$ is separable by a plane, which is not the case in general. $\endgroup$ – leonbloy Jun 9 '13 at 18:04
  • 2
    $\begingroup$ For example, say $n=$, $X_1$ is the north pole, $X_2$ $X_3$ $X_4$ are on a same parallel, equidistant. No possible hemisphere wil select only $X_1$. $\endgroup$ – leonbloy Jun 9 '13 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.