@inproceedings{e7ddc572b5e548f0a35226922a69640d,

title = "Star unfolding of a polytope with applications",

abstract = "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{\textquoteright}Rourke and Schevon.",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Joseph O{\textquoteright}Rourke and Schevon, {Catherine A.}",

year = "1990",

doi = "10.1007/3-540-52846-6_94",

language = "English (US)",

isbn = "9783540528463",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "251--263",

editor = "Rolf Karlsson and Gilbert, {John R.}",

booktitle = "SWAT 1990 - 2nd Scandinavian Workshop on Algorithm Theory, Proceedings",

note = "2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990 ; Conference date: 11-07-1990 Through 14-07-1990",

}