Linear programming and convex hulls made easy
- 1 January 1990
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 211-215
- https://doi.org/10.1145/98524.98570
Abstract
We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time &Ogr;(m). The other constructs convex hulls of n points in Rd, d 3, in expected time &Ogr;(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.Keywords
This publication has 0 references indexed in Scilit: