Linear Time Algorithms for Two- and Three-Variable Linear Programs
Martin Dyer · SIAM Journal on Computing · 1984
$O(n)$ time algorithms for linear programming problems with two or three variables and n constraints are described. The approach uses convexity, dominance of linear functions and linear-time median finding algorithms. The algorithms improve the previously known best bounds of $O(n\log n)$ time for both of these problems.