# 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.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics