Low-dimensional linear programming with violations

Two decades ago, Megiddo and Dyer showed that linear programming in two and three dimensions (and subsequently any constant number of dimensions) can be solved in linear time. In this paper, we consider the linear programming problem with at most k violations, i.e., finding a point inside all but at most k halfspaces, given a set of n halfspaces. We present a simple algorithm in 2-d that runs in O((n + k 2) log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matouˇsek (1994) for many values of k, and is probably near-optimal. An extension of our algorithm in 3-d runs in near O(n + k 11/4 n 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