Chapter 10 - Linear programming

Summary

Several problems, geometric or of other kinds, use the notion of a polytope in d-dimensional space more or less implicitly. The preceding chapters show how to efficiently build the incidence graph which encodes the whole facial structure of a polytope given as the convex hull of a set of points. Using duality, the same algorithms allow one to build the incidence graph of a polytope defined as the intersection of a finite number of half-spaces. It is not always necessary, however, to explicitly enumerate all the faces of the polytope that underlies a problem. This is the case in linear programming problems, which are the topic of this chapter.

Section 10.1 defines what a linear programming problem is, and sets up the terminology commonly used in optimization. Section 10.2 gives a truly simple algorithm that solves this class of problem. Finally, section 10.3 shows how linear programming may be used as an auxiliary for other geometric problems. A linear programming problem may be seen as a shortcut to avoid computing the whole facial structure of some convex hull. Paradoxically, the application we give here is an algorithm that computes the convex hull of n points in dimension d. Besides its simplicity, the interest of the algorithm is mostly that its complexity depends on the output size as well as on the input size. Here, the output size is the number f of faces of all dimensions of the convex hull, and thus ranges widely from O(1) (size of a simplex) to Θ(n^⌊d/2⌋ (size of a maximal polytope).