The densest hemisphere problem

Given a set K of n points on the unit sphere S d in d-dimensional Euclidean space, a hemisphere of Sd is densest if it contains a largest subset of K. In this paper we consider the problem of determining a densest hemisphere and present the following complementary results: (i) a discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary; (ii) when the number d of dimensions is fixed, there exists a polynomial time algorithm which solves the problem in time O(n d−1 log n) on a random access machine with unit cost arithmetic operations.

Authors

• D.S. Johnson
• F.P. Preparata

Keywords

No keywords are indexed for this paper.