Generalised Bagemihl polyhedra and a tight bound on the number of interior Steiner points. (October 2018)

• Record Type: Journal Article
• Authors: Si, Hang; Goerigk, Nadja
• Is Part Of: Computer aided design. Volume 103(2018)
• Page Start: 92
• Page End: 102
• Publication Date: 2018-10
• Subjects: Indecomposable polyhedron -- Irreducible polyhedron -- Tetrahedralization -- Schönhardt polyhedron -- Bagemihl polyhedron -- Steiner points; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.11.009
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We call a 3d polyhedron irreducible if it cannot be decomposed into a set of convex polytopes without adding additional vertices, called Steiner points . Such polyhedra are primitive shapes which are the essence of the reason that will force any 3d convex decomposition algorithm to insert Steiner points in its interior. In this paper, we construct a class of 3d irreducible polyhedra, called generalised Bagemihl polyhedra, with n ≥ 6 vertices. We show that such polyhedra have the same combinatorial structure as the Schönhardt and Bagemihl polyhedra. The most interesting property of these polyhedra is that one can construct it in such a way that it will need more than one interior Steiner point to be triangulated. Given a generalised Bagemihl polyhedron with n ≥ 6 vertices, we show that it can be triangulated by adding at most n − 5 2 interior Steiner points. Moreover, this number is tight. We show an application of using these polyhedra to evaluate the quality of existing 3d boundary recovery tetrahedralisation algorithms.