TY - GEN
T1 - Star unfolding of a polytope with applications
AU - Agarwal, Pankaj K.
AU - Aronov, Boris
AU - O’Rourke, Joseph
AU - Schevon, Catherine A.
N1 - Funding Information:
*Part of the work was carried out when the first two authors were at Courant Institute of Mathematical Sciences, New York University and the fourth author was at the Department of Computer Science, The Johns Hopkins University. The work of the second author was partially supported by an AT&T Bell Laboratories Ph.D. Scholarslfip. The work of the first two authors has also been partially supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center --NSF-STC88-09648. The third author's work is supported by NSF grant CCP~882194. tDIMACS Center, Rutgers University, Piseataway, NJ 08855, USA and Computer Science Department, Duke University, Dzucham, NC 27706, USA tDIMACS Center, Rutgers University, Piscataway, NJ 08855, USA tDepartment of Computer Science, Smith College, Northampton, MA 01063, USA ~AT&T Bell Laboratories, Holmdel, NJ 07733, USA
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.
PY - 1990
Y1 - 1990
N2 - We define the notion of a “star unfolding” of the surface P of a convex polytope with n vertices and use it to construct an algorithm for computing a small superset of the set of all sequences of edges traversed by shortest paths on P. It requires O(n6) time and produces O(n8) sequences, thereby improving an earlier algorithm of Sharir that in O(n8 log n) time produces O(n7) sequences, A variant of our algorithm runs in O(n5 log n) time and produces a more compact representation of size O(n5) for the same set of O(n6) sequences. In addition, we describe an O(n10) time procedure for computing the geodesic diameter of P, which is the maximum possible separation of two points on P, with the distance measured along P, improving an earlier O(n14 log n) algorithm of O’Rourke and Schevon.
AB - We define the notion of a “star unfolding” of the surface P of a convex polytope with n vertices and use it to construct an algorithm for computing a small superset of the set of all sequences of edges traversed by shortest paths on P. It requires O(n6) time and produces O(n8) sequences, thereby improving an earlier algorithm of Sharir that in O(n8 log n) time produces O(n7) sequences, A variant of our algorithm runs in O(n5 log n) time and produces a more compact representation of size O(n5) for the same set of O(n6) sequences. In addition, we describe an O(n10) time procedure for computing the geodesic diameter of P, which is the maximum possible separation of two points on P, with the distance measured along P, improving an earlier O(n14 log n) algorithm of O’Rourke and Schevon.
UR - http://www.scopus.com/inward/record.url?scp=85031907378&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031907378&partnerID=8YFLogxK
U2 - 10.1007/3-540-52846-6_94
DO - 10.1007/3-540-52846-6_94
M3 - Conference contribution
AN - SCOPUS:85031907378
SN - 9783540528463
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 251
EP - 263
BT - SWAT 1990 - 2nd Scandinavian Workshop on Algorithm Theory, Proceedings
A2 - Karlsson, Rolf
A2 - Gilbert, John R.
PB - Springer Verlag
T2 - 2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990
Y2 - 11 July 1990 through 14 July 1990
ER -