## Abstract

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^{2}) 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/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.

Original language | English (US) |
---|---|

Pages (from-to) | 570-579 |

Number of pages | 10 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - 2002 |

Externally published | Yes |

Event | The 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada Duration: Nov 16 2002 → Nov 19 2002 |

## ASJC Scopus subject areas

- Hardware and Architecture