Accession Number:

ADA036361

Title:

The Densest Hemisphere Problem.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1977-01-01

Pagination or Media Count:

27.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE