Geometric Applications of a Randomized Optimization Technique

Abstract.

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.