| 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. |