The Densest Hemisphere Problem.
ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB
Pagination or Media Count:
Given a set of K of n points on the unit sphere S superscript d in d-dimensional Euclidean space, a hemisphere of S superscript d is densest if it contains a largest subset of K. This paper considers the problemm of determing a densest hemisphere and present the following complementary results 1 a discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary 2 when the number d of dimensions is fixed, there exists a polynomial time algorithm which solves the problem with a number of operations On to the d-1th powerlog n on the random access machine with unit cost arithmetic operations.
- Theoretical Mathematics