Go backward to 10 Diameter
Go up to 2 Coordinate Descriptions
Go forward to 12 Volume

11 Minimum Triangulation

Input: Polytope P in V-description, positive integer K
Output: "Yes" if P has a triangulation of size K or less, "No" otherwise
Status (general): NP-complete
Status (fixed dim.): NP-complete
A triangulation T of a d-polytope P is a collection of d-simplices, whose union is P, their vertices are vertices of P, and any two simplices intersect in a common face (which might be empty). In particular, T is a (pure) d-dimensional geometric simplicial complex (see Section 7). The size of T is the number of its d-simplices. Every (convex) polytope admits a triangulation.

Below, De Loera, and Richter-Gebert [4][5] proved that MINIMUM TRIANGULATION is NP-complete for (fixed) d ³ 3. Furthermore, it is NP-hard to compute a triangulation of minimal size for (fixed) d ³ 3.