Small-dimensional linear programming and convex hulls made easy (Q1176319)

In the theory of linear programming it was shown that if the number of variables in a linear program is considered constant, then the linear program can be solved in time that is in the number of its constraints. This paper presents two randomized algorithms. One solves linear programs with a constant number of variables whose expected running time is linear in the number of its constraints. The second part concerns the problem of constructing the convex hull of \(n\) points in the Euclidean space \(R^ d\), \(d>3\), in expected time \(O(n^{[d/2]})\). The advantage of the results lies in the simplicity of the algorithms.