# finding a hemisphere that contains all points of a given set S

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?

• 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. Apr 13, 2022 at 14:38
• 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. Apr 14, 2022 at 7:40
• There is nothing overkill about using linear programming. In fixed dimension, it has linear complexity, that's faster than computing the convex hull. Jun 13, 2022 at 22:57

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.