Low-dimensional linear programming with violations

Two decades ago, Megiddo and Dyer 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²) log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matoušek (1994) and is probably near-optimal for all k ≪ n/2. A (theoretical) extension of our algorithm is 3-d runs in near O(n + k^11/4n^1/4) expected time. Interestingly, the idea is based on concave-chain decompositions (or covers) of the (≤ 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.