Geometric Applications of a Randomized Optimization Technique
Geometric Applications of a Randomized Optimization Technique
复制标题
随机优化技术的几何应用
DOI：
10.1145/276884.276915
复制
发表时间：
1998
影响因子：
0.8
通讯作者：
Timothy M. Chan
中科院分区：
文献类型：
--
作者：
Timothy M. Chan
抽象的。我们提出了一种简单、通用、随机化的方法，将某些几何优化问题归结为相应的决策问题。这些减少只增加了预期的时间复杂度一个常量因素，并消除了以前的、通常更复杂的确定性方法(如参数搜索)中的额外对数因素。从而为计算几何中的各种问题得到了更快的算法：寻找最小k点子集，平移匹配点集，计算直线p中心和离散1中心，以及求解具有k个违规的线性规划。
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.