Link to FAQ in Polyhedral Computation by Fukuda

Here is a link to the extremely useful and well written FAQ in polyhedral computation by Fukuda. Here is a PDF version.


See the sections on face-lattice, polarity aka. duality and Minkowski-Weyl. The number of facets of a d-dimensional, n-vertex polytope grows linearly with n. However, its slope is so high that it grows intractable within no time (fascinating!).

Note: See the sub-sections where many problems, simple and hard, are discussed.

11/25: Probably the polylib-page on Polyhedra , with material taken from Schrijver's book is useful for definitions. Read the rest of this entry >>

Convex Polytopes and notes from Develin's works

Mike Develin is a Mathematician who has written a compendium (PDF link) to accompany Ziegler's wonderful book. Also, the first two chapters of his thesis (PDF link) are a great read for anyone interested in convex polyhedra. Some notes:

On homogenization and equivalence:

Given a polytope P\subset \mathbb{R}^d, we can form a cone associated to it by considering the cone of all points {(1,v)} where v \in V. Two crucial points: (1) The shape of the polytope can be recovered by intersecting this cone with the hyperplane x = 1. (2) You might notice that the shape of the polytope we obtain is dependent on the orientation of the polyhedral cone in R^d. This leads to the very important concept of projective equivalence. Two polytopes are defined to be projectively equivalent if they can be obtained as cross-sections of the same polyhedral cone one dimension higher; this notion of equivalance is stronger than the notion of combinatorial equivalence, where two polytopes are equivalent if their faces have same combinatorial structure, and weaker than the notion of affine equivalence, which relates polytopes which are affinely isomorphic to each other.

On polarity:

the face-lattice L(P) is just a partially ordered set, or poset with elements being the faces of the polytope and F < G if F \subseteq G.
...
One key property of polytopes is that the intersection of any two faces is itself a face, which corresponds to the fact that any two elements of the poset have a unique maximal lower bound. The aforementioned notion of combinatorial equivalence corresponds to two polytopes having the same face lattice.

With face lattice, it is easy to give a combinatorial description of the polar polytope P^\Delta. The polar polytope realizes the full power of the duality between the two formulations of polytopes, in terms of vertices and in terms of inequalities. Assuming that P is full-dimensional (embedded in R^d, where d is the dimension of P), P^\Delta is the object in the dual space V^* consisting of those linear functionals f for which f(x) \le 1 holds everywhere on P. To do this, we need to pick the position of the origin inside P, but once we have done this, the entire combinatorial and indeed projective type of P^\Delta is determined. Furthermore, the face-lattice of P^\Delta is precisely the opposite poset of L(P).
...

... the Farkas lemma implies that the polar polytope is the convex hull of the facet-defining functionals, which provides a natural correspondence between the vertices of P^\Delta and the facets of P. In fact, the lattices are isomorphic under this correspondence; the face lattice is completely determined by which subsets of {1,2,...,n} are facets, so this, along with the fact that the vertices of P correspond to the facets of P (as constraint f(x) <= 1 on P is equivalent to the intersection of half-spaces f(v) <= 1 for v \in V) exhibits explicit correspondence.

Thanks Mike!

Postscript (11/05): The chapter "Basic Properties of Convex Polytopes" is available via the following link: ftp://ftp.math.tu-berlin.de/pub/combi/ziegler/WWW/archiv/049polychap2.ps.gz(with thanks to Prof. Ziegler). The chapter is from the book: Handbook of Discrete and Computational Geometry with the following table of contents. Read the rest of this entry >>