2

Consider the $n$-dimensional hypersphere, $\mathbb{S}^n$. Given a set of points, $T$, on the surface of $\mathbb{S}^n$, we wish to determine whether at least one $t \in T$ lies in (including on the boundary of) any possible hemisphere of $\mathbb{S}^n$.

  • what are the most elegant sufficiency conditions?
  • what are the most efficient sufficiency conditions?

In the special case in which $t, t' \in T$ are antipodal, then we are done.

As this is not a Hamiltonian path problem (so, not as obviously threatened by greedy algorithms?), a 'nearest antipodes' approach seems a good start:

  1. start with the most isolated $t \in T$;
  2. if its antipode $t'$ is in $T$, stop;
  3. otherwise, determine the closest $t'' \in T$ to $t' \ldots$

The $n = 2$ case was presented in the 2017 World Finals of Code Jam, as a problem in 'omnicircumnavigation'.

Colin Rowat
  • 181
  • Given any set of points in $\mathbb{S}^n$? – user829347 Feb 14 '22 at 21:59
  • Yes: $T$ can be any set of points on the surface of $\mathbb{S}^n$. Given some $T$, we want to know whether at least one $t \in T$ lies in any possible hemisphere of $\mathbb{S}^n$. If my original question can be improved, please let me know: I may be missing nuances. – Colin Rowat Feb 15 '22 at 13:16
  • But if your set of points $T$ are all contained in one hemisphere (without boundary), then the opposite hemisphere (with boundary) contains none of them. Maybe I'm missing something. Think of $S^2$ as the earth. If you take a set of points strictly in the northern hemisphere, none of these points are either in the southern hemisphere or on the equator, so there is a hemisphere containing none of them – user829347 Feb 15 '22 at 14:18
  • Yes, correct: in your example, we can easily determine that $T$ fails the test. We want a simple condition that generalises from "south of the equator" to "on one side of any possible great circle". – Colin Rowat Feb 15 '22 at 16:32

0 Answers0