On the Number of Star-Shaped Polygons and Polyhedra
Roland Ulber · 1999
We show that the maximum number of strictly star-shaped polygons through a given set of n points in the plane is \\Theta(n 4 ). Our proof is constructive, i.e. we supply a construction which yields the stated number of polygons. We further present lower and upper bounds for the case of unrestricted star-shaped polygons. Extending the subject into three dimensions, we give a tight bound of \\Theta(n 9 ) on the number of distinct sets of star-shaped polyhedra. 1 Introduction Reconstructing an initial geometric object from partial features has always been of major interest in computational geometry. Many well-studied problems in two and three dimensions can be seen from this point of view, for example triangulating a simple polygon [1] (or tetrahedralizing a polyhedron [6], respectively), finding the Delaunay triangulation of a point set, reconstructing three-dimensional objects from cross-sectional slices [2], or finding a triangulation of a three-dimensional polygon [5]. Instead of...