Abstract
The star unfolding of a convex polytope with respect to a pointx on its surface is obtained by cutting the surface along the shortest paths fromx to every vertex, and flattening the surface on the plane. We establish two main properties of the star unfolding:
-
1.
It does not self-overlap: it is a simple polygon.
-
2.
The ridge tree in the unfolding, which is the locus of points with more than one shortest path fromx, is precisely the Voronoi diagram of the images ofx, restricted to the unfolding.
These two properties permit conceptual simplification of several algorithms concerned with shortest paths on polytopes, and sometimes a worst-case complexity improvement as well:
-
•
The construction of the ridge tree (in preparation for shortest-path queries, for instance) can be achieved by an especially simpleO(n 2) algorithm. This is no worst-case complexity improvement, but a considerable simplification nonetheless.
-
•
The exact set of all shortest-path “edge sequences” on a polytope can be found by an algorithm considerably simpler than was known previously, with a time improvement of roughly a factor ofn over the old bound ofO(n 7 logn).
-
•
The geodesic diameter of a polygon can be found inO(n 9 logn) time, an improvement of the previous bestO(n 10) algorithm.
Our results suggest conjectures on “unfoldings” of general convex surfaces.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal, B. Aronov, J. O'Rourke, and C. Schevon. Star unfolding of a polytope with applications. In J. R. Gilbert and R. Karlsson, editors,Proc. of 2nd Scandanavian Workshop on Algorithm Theory, pages 251–263. Lecture Notes in Computer Science, Vol 447. Springer-Verlag, Berlin, 1990.
P. K. Agarwal, B. Aronov, J. O'Rourke, and C. Schevon. The star unfolding of a polytope. Technical report, Smith College, 1992. Full version of [AAOS1]; currently under revision.
A. D. Aleksandrov.Die Innere Geometrie der Konvexen Flächen. Mathematische Lehrbücher und Monographien. Akademie-Verlag, Berlin, 1955.
A. D. Aleksandrov.Konvexe Polyeder. Mathematische Lehrbücher und Monographien. Akademie-Verlag, Berlin, 1958.
A. D. Aleksandrov and V. A. Zalgaller.Intrinsic Geometry of Surfaces. American Mathematical Society, Providence, RI, 1967. Translation of the 1962 Russian original.
H. Buseman.Convex Surfaces. Wiley-Interscience, New York, 1958.
J. Chen and Y. Han. Shortest paths on a polyhedron. InProc. of 6th ACM Symposium on Computational Geometry, pages 360–369, 1990.
M. Henle.A Combinatorial Introduction to Topology. Freeman, San Francisco, CA, 1979.
S. Kobayashi. On conjugate and cut loci. In S. S. Chern, editor,Studies in Global Geometry and Analysis, pages 96–122. Mathematical Association of America, Washington, DC, 1967.
D. T. Lee. Medial axis transformation of a planar shape.IEEE Trans. Pattern Anal. Mach. Intell., 4:363–369, 1982.
A. V. Pogorelov.Extrinsic Geometry of Convex Surfaces. Translations of Mathematical Monographs, Vol. 35. American Mathematical Society, Providence, RI, 1973.
R. Rasch. Shortest paths along a convex polyhedron. Manuscript, Berlin, 1990.
M. Sharir and A. Schorr. On shortest paths in polyhedral spaces.SIAM J. Comput., 15:193–215, 1986.
Author information
Authors and Affiliations
Additional information
Part of the research for this paper was carried out while the first author was at the DIMACS Center, Rutgers University (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. The second author's research was supported by NSF Grant CCR-882194.
Rights and permissions
About this article
Cite this article
Aronov, B., O'Rourke, J. Nonoverlap of the star unfolding. Discrete Comput Geom 8, 219–250 (1992). https://doi.org/10.1007/BF02293047
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02293047