| Abstract (2008) | |||||||||||||
Abstract | |||||||||||||
| It is well known that one can always polygonize a set ¥ of ¦¨§� © points in the plane (not all on a line), i.e., construct a simple polygon � whose vertices are precisely the given points in ¥. For example, the shortest circuit through ¥ is a simple polygon. In 1994 Branko Grünbaum showed that an analogous theorem holds in �� �. More precisely, if ¥ is a set of ¦�§� � points in �� � (not all of which are coplanar) then it is always possible to polyhedronize ¥ , i,e., construct a simple (sphere-like) polyhedron � such that the vertices of � are precisely the given points in ¥. Grünbaum’s constructive proof may yield Schönhardt polyhedra that cannot be triangulated. In this paper several alternative algorithms are proposed for constructing such polyhedra induced by a set of points, 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. We show that polyhedronizations with a variety of such useful properties can be computed efficiently in ����¦�������¦� � time. Furthermore, we show that a tetrahedralized, �� �-monotonic, polyhedronization of ¥ can be computed in time ����¦������� � , for any ���� �. 1 | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||