Linear programming and convex hulls made easy
Raimund Seidel · 1990
We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time Ο(m). The other constructs convex hulls of n points in Rd, d > 3, in expected time Ο(n⌈d/2⌉). In both bounds d is considered to be a constant. In the linear programming algorithm the dependence of the time bound on d is of the form d!. The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses.