Low-dimensional linear programming with violations

Two decades ago, Megiddo and Dyer showed that linear programming (LP) in two and three dimensions (and subsequently any constant number of dimensions) can be solved in linear time. In this paper, we consider the LP problem with at most κ violations, i.e., finding a point inside all but at most κ halfspaces, given a set of n halfspaces. We present a simple algorithm in two dimensions that runs in O((n + κ²) log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matoušek (1994) for many values of κ and is probably near-optimal. An extension of our algorithm in three dimensions runs in near O(n + κ^11/4n^1/4) expected time. Interestingly, the idea is based on concave-chain decompositions (or covers) of the (≤ κ)-level, previously used in proving combinatorial κ-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 κ points. We also discuss related problems of finding local minima in levels.