How to prove that a set of facets are all the facets of a convex polytope.

Question

Say that you know all the vertices of a polytope P, and a set of facet defining hyperplanes that you guess give all the facets of P. What are some good ways to try to prove that the guess is right?

A common idea seems to be to find a way to linearly optimize over the polytope defined by the facets and then show that you always end up in one of the vertices of P. Another type of argument involves the volume of the polytopes. There is also algorithms that involve constructing a simplicial complex of the given data and then compute homology. Are there other common teqniques?

Are there any good ways to prove that the guess is wrong?

Answer 1

Hi,

The question itself and all answers seem to be "practice-oriented" but as far as the complexity status of the problem is concerned then you are speaking about famous L.Lovasz's "polytope- polyhedron question". Namely, to check whether a polytope given by vertices coincides with a polyhedron given by facets. Note, that the lengths of the vertex and, respectively, the facet descriptions may differ exponentially and thus we should speak about incremental polynomial algorithms. Say, if a polyhedron is given by facets you should find a new vertex in polynomial time with respect to the input and the length of the list of already calculated vertices. In this format the question is still open for (bounded) polytopes but is proved to be NP-hard for (unbounded) polyhedrons (see, http://portal.acm.org/citation.cfm?id=1109640 and references therein)

Answer 2

Well, something that comes to mind is this... Suppose your facet-defining hyperplanes have equations $v^i \cdot x = a_i$ and you're working in $n$ dimensions. Suppose that $v^i \cdot x < a_i$ inside $P$. (Which way the inequality goes can be determined by testing the vertices of $P$). Then a vertex of the polytope defined by your hyperplanes is a point where $v^i \cdot x = a_i$ for $n$ independent $v^i$ and where $v^i \cdot x \leq a_i$ for the other $v^i$. You can find each such vertex by solving some linear equations and then checking some inequalities hold at the solution. If the resulting set of vertices obtained is exactly the vertex set of $P$, you're in business. Otherwise, you're not.

Answer 3

Let V be the set of vertices, P their convex hull, and Q the polytope defined by the hyperplanes. If P is assumed to be simple, it suffices to check that each x in V is also a vertex of Q.

By your assumptions, P is contained in Q. Let x be a vertex of P. Assume that P is n-dimensional. By my assumption of simpleness, x has n facet-supporting hyperplanes of P through it. These hyperplanes must all be hyperplanes of Q; otherwise, x would not be a vertex of Q. Every facet of P includes some vertex of P (rather trivially) so this shows that all the facet-supporting hyperplanes of P are among the defining hyperplanes of Q. Thus Q is contained in P, and so Q=P.

Answer 4

The unhelpful suggestion is to perform the complete dual cone calculation (using available software) and then see if the answer matches your initial guess. Unfortunately, my pessimistic intuition is that in the general case, you cannot expect to do much better than this, even in the case where the initial guess is correct. You might get lucky optimizing in random directions in the dual space and find a hyperplane you missed, but in high dimensions there are too many directions and things are just subtle and elusive.

Three things that make the problem easier:

1. If the polytope P is known to be simple,
2. if the intersection of half-spaces Q is known to be simplicial, or
3. if the dimension is small.

The first case was covered by the answer given by Hugh Thomas: just verify that each vertex is a vertex of Q. In the second case the same verification suffices by duality, where the roles of facet-defining hyperplanes and extreme points (genuine vertices) are exchanged. In the third case you can construct the entire face lattice inductively. The hard case is when the dimension is high, which means that even if there are relatively few vertices and facets, the number of intermediate faces can be unmanageable.

Unfortunately it is not even easy in general to verify whether one of the first two conditions holds. An instructive example is the case where Q is a cube and P is obtained by deleting a pair of opposite vertices from Q (giving a flattened octahedron). In this case every vertex of P is a vertex of Q, every facet of Q restricts to a facet of P, P looks simple when checked by Q, and Q looks simplicial when checked by P, but they are not equal, P is not simple, and Q is not simplicial. (Fortunately, the dimension is low!)

Having expressed pessimism about there being any good solution, let me at least offer a bad one—likely to run much too slowly on any interesting example—that essentially does construct the face lattice (inefficiently) as suggested for low dimensions. We assume that it has already been verified (not difficult) that every vertex defining P does lie within Q (and therefore that every hyperplane defining Q lies outside the interior of P) but for the purposes of induction we will not insist that every every "vertex" is an extreme point of P or that every hyperplane gives a facet of Q; when we encounter such redundancies we will silently discard them for the purposes of that stage of the algorithm. (On the other hand, we do require that vertices are distinct and hyperplanes are distinct, and we delete repetitions before doing anything else.) What we will verify instead is that every vertex of Q is in the list for P, and that every facet of P comes from the list of hyperplanes for Q. If that ever fails, we report it and quit.

Firstly, every polygon is both simple and simplicial, which makes the case of two dimensions easy: Recursively eliminate any vertex of P that does not lie on two lines of Q, or any line of Q that does not contain two vertices of P. If anything is left when you are done (again, assuming P was contained in Q), they were always equal.

Now, suppose you have a solution in dimension d with which you are happy. In dimension $d+1$, you do as follows: For each hyperplane H in turn, identify the set of vertices incident to it, and verify that they span it affinely. (Otherwise H is redundant, so just continue on to the next hyperplane.) The convex hull of these vertices defines a polytope P' of dimension d within H, and the (largely redundant) intersection of all other halfspaces with H defines a polytope Q' which contains P'. The polytopes P and Q are equal if and only if P' and Q' are equal for every non-redundant hyperplane H.

Lather, rinse, repeat.

Answer 5

You can directly compute the facets with duality theory. Dualize your vertices, compute their convex hull, and dualize the hull's vertices. Then you can directly compare them with your conjectured facets.