caa a22 4500 469075279 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920301xx s 000 0 eng 10.1007/BF02187840 doi (NATIONALLICENCE)springer-10.1007/BF02187840 On the difficulty of triangulating three-dimensional Nonconvex Polyhedra [Elektronische Daten] [Jim Ruppert, Raimund Seidel] A number of different polyhedraldecomposition problems have previously been studied, most notably the problem of triangulating a simple polygon. We are concerned with thepolyhedron triangulation problem: decomposing a three-dimensional polyhedron into a set of nonoverlapping tetrahedra whose vertices must be vertices of the polyhedron. It has previously been shown that some polyhedra cannot be triangulated in this fashion. We show that the problem of deciding whether a given polyhedron can be triangulated is NP-complete, and hence likely to be computationally intractable. The problem remains NP-complete when restricted to the case of star-shaped polyhedra. Various versions of the question of how many Steiner points are needed to triangulate a polyhedron also turn out to be NP-hard. Springer-Verlag New York Inc., 1992 Ruppert Jim Computer Science Division, University of California at Berkeley, 94720, Berkeley, CA, USA aut Seidel Raimund Computer Science Division, University of California at Berkeley, 94720, Berkeley, CA, USA aut Discrete & Computational Geometry Springer New York 7/3(1992-03-01), 227-253 0179-5376 7:3<227 1992 7 454 https://doi.org/10.1007/BF02187840 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187840 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ruppert Jim Computer Science Division, University of California at Berkeley, 94720, Berkeley, CA, USA aut NATIONALLICENCE 700 1- Seidel Raimund Computer Science Division, University of California at Berkeley, 94720, Berkeley, CA, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/3(1992-03-01), 227-253 0179-5376 7:3<227 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer