Finding vertices of a polytope?

Question

Assume that in 3D we have a polytope defined by the intersection of halfspaces.

A half space is the set of all solutions of a linear inequality $P = N \cdot x + c \leq 0$ Where $N$ is the normal to the half space.

The polytope is thus the boundary of $\cap_{i=0} P_i$ $P_i = N_i \cdot x + c_i \leq 0$.

In 3D all vertices must be intersections of at least 3 planes. i.e. all vertices are a subset of all points such that:

$$P_i = P_j = P_k = 0$$

Which is a trivial 3x3 system that can be easily solved.

However, the total number of points that you get out of this is exponentially larger than the actual number of points on the polytope.

For example in this diagram:

The top plane intersects the other 2 at points which are not vertices of the polytope.

Answer 1

(I'm going to use the word “polyhedron” instead of “polytope” because I haven't considered how to generalize it to more dimensions.)

1. Being constructed of the intersection of half-spaces, the polyhedron must be convex; the interior volume is a region containing none of the planes.

2. We can classify the intersection points of 3 unequal planes as follows:

   • There cannot be an intersection point within the polyhedron, because per (1), none of the planes intersect the polyhedron.
   • If it is on the surface, then it must be a vertex; it cannot lie on an edge or face because if it did, that would contradict the 3 planes defining a point.
   • If it is outside the polyhedron, then it must not be a vertex.

3. If an intersection point lies within the outside half of any one of the half-spaces making up the polyhedron, then it cannot be inside or on the surface of the polyhedron per (1), and therefore cannot be a vertex per (2).

4. If an intersection point does not lie within the outside half of any half-space, then it cannot be inside per (1), so it must be on the surface of the polyhedron, and therefore per (2) must be a vertex.

Therefore, it suffices to discard all intersections which are outside any one of the half-spaces.

This can be seen as applying the separating axis theorem to the points; every plane defines a potential separating axis.

Answer 2

You can use an incremental approach.

In 3D, it works as follows:

• Assume that as some point you have constructed the (possibly open) polytope defined by the $k$ first planes.

• Consider the next plane and change the coordinate system so that the equation simplifies to $z=0$.

• For every edge of the polytope, check if the endpoints belong to the same half-plane defined by the plane ($z$ sign).

• If both have $z>0$, keep the edge; if both have $z<0$, discard the edge; otherwise, compute the intersection point of the edge with the plane and trim the edge. Finally, join the intersection points to form a convex section polygon.

• Repeat with the remaining planes.

This method cannot avoid the $O(n^3)$ behavior in the worst case (no method can) but if you are lucky it can keep the number of useless vertex computations to a low value. (At best, $O(nm)$ intersections for $n$ planes and $m$ vertices in the solution.)