Fixed-dimensional linear programming queries made easy

Research output: Contribution to conferencePaperpeer-review

Abstract

We derive two results from Clarkson's randomized algorithm for linear programming in a fixed dimension d. The first is a simple general method that reduces the problem of answering linear programming queries to the problem of answering halfspace range queries. For example, this yields a randomized data structure with O(n) space and O(n1-1/[d/2] 20(log(*) n)) query time for linear programming on n halfspaces (d > 3). The second result is a simpler proof of the following: a sequence of q linear programming queries on n halfspaces can be answered in O(n log q) time, if q ≤ nα(d) for a certain constant αd > 0. Unlike previous methods, our algorithms do not require parametric searching.

Original languageEnglish (US)
Pages284-290
Number of pages7
DOIs
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA
Duration: May 24 1996May 26 1996

Other

OtherProceedings of the 1996 12th Annual Symposium on Computational Geometry
CityPhiladelphia, PA, USA
Period5/24/965/26/96

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Fixed-dimensional linear programming queries made easy'. Together they form a unique fingerprint.

Cite this