Geometric Applications of a Randomized Optimization Technique |
| |
Authors: | T M Chan |
| |
Institution: | (1) Current address: Department of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada. tmchan@math.uwaterloo.ca., CA;(2) Department of Mathematics and Computer Science, University of Miami, Coral Gables, FL 33124-4250, USA, tchan@cs.miami.edu, US |
| |
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.
Received May 23, 1998, and in revised form March 29, 1999. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|