Low-dimensional linear programming with violations

Research output: Contribution to journalConference articlepeer-review


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 + k2) 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 + k11/4n1/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 languageEnglish (US)
Pages (from-to)570-579
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2002
Externally publishedYes
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Low-dimensional linear programming with violations'. Together they form a unique fingerprint.

Cite this