Abstract.
We prove that it is NP-hard to decide whether a polyhedral 3-ball can be triangulated with k simplices. The construction also implies that it is difficult to find the minimal triangulation of such a 3-ball. A lifting argument is used to transfer the result also to triangulations of boundaries of 4-polytopes.
The proof is constructive and translates a variant of the 3-SAT problem into an instance of a concrete polyhedral 3-ball for which it is difficult to find a minimal triangulation.
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received February 17, 1999, and in revised form October 20, 1999. Online publication May 16, 2000.
Rights and permissions
About this article
Cite this article
Richter-Gebert, J. Finding Small Triangulations of Polytope Boundaries Is Hard. Discrete Comput Geom 24, 503–518 (2000). https://doi.org/10.1007/s004540010052
Issue Date:
DOI: https://doi.org/10.1007/s004540010052