2
$\begingroup$

Let $S$ be a finite set of points on the unit sphere $\mathbb{S}^2$. My question would be: is there an easy way to either find a great circle $C$ such that all points in $S$ are inside one of the hemispheres defined by $C$ or return that such a great circle does not exist.

This can of course also be seen as a problem in 3D, i.e. does there exist a plane through the origin, such that one of the halfplanes contains all of the points.

The only thing I could think of was like a "perceptron" style algorithm, but I'm not sure, if that algorithm would terminate, if a solution exists and also when to stop if it does not exist.

Does anyone have a "more sophisticated" idea?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I may be wrong, but I think that computing the convex hull of $S$ and checking if the origin is inside of it may do the trick. $\endgroup$
    – Nathaniel
    Commented Apr 13, 2022 at 14:38
  • $\begingroup$ I think that this would work too! thanks. Now the question that remains is: how to get the great circle/plane that induces the hemisphere/halfspace. I think I could solve it using a linear program but it seems like using a sledgehammer to crack a nut. $\endgroup$
    – Philip Mayer
    Commented Apr 14, 2022 at 7:40
  • $\begingroup$ There is nothing overkill about using linear programming. In fixed dimension, it has linear complexity, that's faster than computing the convex hull. $\endgroup$
    – Marc Glisse
    Commented Jun 13, 2022 at 22:57

1 Answer 1

Reset to default
1
$\begingroup$

As suggested by Nathaniel, first find the convex hull of $S$. Now note that there would exist a plane of the convex hull with the property that its one side contains all the points in $S$ and the other side contains the origin. Let this plane be $ax + by + cz = d$. Then, the plane passing through the origin would be $ax + by +cz = 0$; it would induce the required halfspace.

You can get the plane $ax + by + cz = d$ by finding the convex hull in $O(n \log n)$ and verifying the property for each plane in $O(n)$ time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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