On Polyhedra Induced by Point Sets in Space.
Ferrán Hurtado, Godfried T. Toussaint, Joan Trias · 2003
Given a set S of n 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 P are precisely the given points in S. For example, the shortest circuit through S must be such a simple polygon [20]. In 1994 Grünbaum [13] showed that an analogous theorem holds in 3-dimensional space. More precisely, if S is a setof 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 P are precisely the given points in S. Grünbaum's constructive proof may yield Sch dt polyhedra that cannot be triangulated [?]. In this paper we propose several alternative algorithms for constructing such polyhedra induced by a set of points. Our methods yield polyhedra which not only may always be triangulated, but which enjoy several other use f] 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 varietyof such usef ul properties can be computed efficiently in O(n log n) time.