Electronic Resource
Springer
Discrete & computational geometry
24 (2000), S. 503-518
ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004540010052
Permalink
| Library |
Location |
Call Number |
Volume/Issue/Year |
Availability |
