caa a22 4500 46907499X CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF02293047 doi (NATIONALLICENCE)springer-10.1007/BF02293047 Nonoverlap of the star unfolding [Elektronische Daten] [Boris Aronov, Joseph O'Rourke] 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. Springer-Verlag New York Inc., 1992 Aronov Boris Computer Science Department, Polytechnic University, 11201, Brooklyn, NY, USA aut O'Rourke Joseph Department of Computer Science, Smith College, 01063, Northampton, MA, USA aut Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 219-250 0179-5376 8:3<219 1992 8 454 https://doi.org/10.1007/BF02293047 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293047 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Aronov Boris Computer Science Department, Polytechnic University, 11201, Brooklyn, NY, USA aut NATIONALLICENCE 700 1- O'Rourke Joseph Department of Computer Science, Smith College, 01063, Northampton, MA, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 219-250 0179-5376 8:3<219 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer