Low-dimensional linear programming with violations

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²) 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 ≪ n/2. A (theoretical) extension of our algorithm in 3-d runs in near O(n + k¹¹4/n¹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.