Low-dimensional linear programming with violations
Low-dimensional linear programming with violations
复制标题
具有违规的低维线性规划
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan
中科院分区：
文献类型：
--
作者：
Timothy M. Chan
Megiddo（1984）和Dyer（1984）证明了二维和三维的线性规划（以及随后的任何常数维数）可以在线性时间内求解。在本文中，我们考虑线性规划与最多k个违规：找到一个点内的所有，但最多k个n给定的半空间。我们给出了一个简单的算法在2-d运行在O（（n + k/sup 2/）log n）的预期时间;这是快于早期的算法由埃弗雷特，罗伯特，和货车Kreveld（1993）和Matousek（1994），可能是近最佳的所有k /spl Lt/ n/2。我们的算法在3-d的（理论）扩展运行在近O（n + k/sup 11/4/n/sup 1/4/）的预期时间。有趣的是，该思想基于先前在证明组合k层边界中使用的（k）层的凹链分解（或覆盖）。在平面上的应用包括改进的算法，用于找到一条在一组双色点中错误分类最少的线，以及找到包围除k点之外的所有点的最小圆。我们还讨论了在水平中寻找局部极小点的相关问题。
Megiddo (1984) and Dyer (1984) showed that linear programming in 2 and 3 dimensions (and subsequently, any constant number of dimensions) can be solved in linear time. In this paper, we consider linear programming with at most k violations: finding a point inside all but at most k of n given halfspaces. We give a simple algorithm in 2-d that runs in O((n + k/sup 2/) log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matousek (1994) and is probably near-optimal for all k /spl Lt/ n/2. A (theoretical) extension of our algorithm in 3-d runs in near O(n + k/sup 11/4/n/sup 1/4/) expected time. Interestingly; the idea is based on concave-chain decompositions (or covers) of the (/spl les/ k)-level, previously used in proving combinatorial k -level bounds. Applications in the plane include improved algorithms for finding a line that misclassifies the fewest among a set of bichromatic points, and finding the smallest circle enclosing all but k points. We also discuss related problems of finding local minima in levels.