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 |