$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(nlog n) time for both of these problems.
No takes yet. Share an insight, caveat, or question.
Martin Dyer (1984) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: