The Densest Hemisphere Problem.

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 O((n to the (d-1)th power)log n) on the random access machine with unit cost arithmetic operations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1977
Accession Number
ADA036361

Entities

People

  • D. S. Johnson
  • Franco P. Preparata

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms
  • Counter IED
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Arithmetic
  • Boundaries
  • Computer Programming
  • Electrical Engineering
  • Hemispheres
  • Illinois
  • Linear Programming
  • New Jersey
  • Numbers
  • Operations Research
  • Political Science
  • Polynomials
  • Statistical Analysis
  • United States
  • United States Government

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Approximation Theory.
  • Fluid Dynamics.

Technology Areas

  • Space