| On Polyhedr Induced by Point Sets in Space (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Given a set Sof 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 Grunbaum [13]showed that an analogous theorem holds in 3-dimensional space. More precisely, if S is a setof points in space (not allof which are coplanar) then it is always possible to polyh dronize S, i,e., construct a simple (sphere-like) polyhedron P such that the P are precisely the given points in S.Grunbaum's constructive proof may yield Sch dt polyhedra that cannot be triangulated [?]. In this paper we propose several alternative algorithmsf or 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 usef] properties as well. Such properties include polyhedra that are star-shaped, have hamiltonian skeletons, and admit e#cient point location queries. Furthermore, we show that polyh dronizations with a varietyof such usef ul properties can be computed e#ciently in O(n log n)time. 1 IntroductiY 1964Hugo Steinhaus po sed thefokP wingproj0 m [25]. There are n ints lying in a plane,no threeo f them lyingo n the same straight line. Is it always po#kPk# to find a cloQ# po lygo with nno n-intersecting sideswho se vertices are these n ints? Then he pro ceeded to give a clever pro o byinductio that this is true. His pro o remo ves an extreme po into f the set and byinductio assumes the remaining n 1 po0 ts admit such a po#8338 Then bytrial and erro he searches f o an edge o this po lygo that is co mpletelyvisible fro the remo ved po int. A direct implementatio no f his pr... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||