| On Polyhedra Induced by Point Sets in Space ∗ (2008) | |||||||||||||
Abstract | |||||||||||||
| Given a set S of n ≥ 3 points in the plane (not all on a line) it is well known that it is always possible to polygonize S, i.e., construct a simple polygon P such that the vertices of P are precisely the given points in S. In 1994 Grünbaum showed that an analogous theorem holds in 3-dimensional space. More precisely, if S is a set of n points in space (not all of which are coplanar) then it is always possible to polyhedronize S, i.e., construct a simple (sphere-like) polyhedron P such that the vertices of P are precisely the given points in S. Grünbaum’s constructive proof may yield Schönhardt polyhedra that cannot be triangulated. In this paper several alternative algorithms are proposed for constructing polyhedra induced by a set of points in space, which may always be triangulated, and which enjoy several other useful properties as well. Such properties include polyhedra that are star-shaped, have Hamiltonian skeletons, and admit efficient point location queries. Furthermore, we show that polyhedronizations with a variety of these properties can be computed in O(n log n) time. 1 | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||