Star unfolding of a polytope with applications

Conference Paper

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(n ) time and produces O(n ) sequences, thereby improving an earlier algorithm of Sharir that in O(n log n) time produces O(n ) sequences, A variant of our algorithm runs in O(n log n) time and produces a more compact representation of size O(n ) for the same set of O(n ) sequences. In addition, we describe an O(n ) 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(n log n) algorithm of O’Rourke and Schevon. 6 8 8 7 5 5 6 10 14

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; O’Rourke, J; Schevon, CA

Published Date

  • January 1, 1990

Published In

Volume / Issue

  • 447 LNCS /

Start / End Page

  • 251 - 263

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540528463

Digital Object Identifier (DOI)

  • 10.1007/3-540-52846-6_94

Citation Source

  • Scopus