Geometric applications of a randomized optimization technique

Research output: Contribution to journalArticlepeer-review


We propose a simple, general, randomized technique to reduce certain geometric optimization problems to their corresponding decision problems. These reductions increase the expected time complexity by only a constant factor and eliminate extra logarithmic factors in previous, often more complicated, deterministic approaches (such as parametric searching). Faster algorithms are thus obtained for a variety of problems in computational geometry: finding minimal k-point subsets, matching point sets under translation, computing rectilinear p-centers and discrete 1-centers, and solving linear programs with k violations.

Original languageEnglish (US)
Pages (from-to)547-567
Number of pages21
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - Dec 1999
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Geometric applications of a randomized optimization technique'. Together they form a unique fingerprint.

Cite this