Star unfolding of a polytope with applications

Pankaj K. Agarwal, Boris Aronov, Joseph O'Rourke, Catherine A. Schevon

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We introduce the notion of a star unfolding of the surface P of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on P. The first algorithm computes the edge sequences traversed by shortest paths on P in time O(n6β(n) log n), where β(n) is an extremely slowly growing function. A much simpler O(n6) time algorithm that finds a small superset of all such edge sequences is also sketched. The second algorithm is an O(n8 log n) time procedure for computing the geodesic diameter of P: the maximum possible separation of two points on P with the distance measured along P. Finally, we describe an algorithm that preprocesses P into a data structure that can efficiently answer the queries of the following form: "Given two points, what is the length of the shortest path connecting them?" Given a parameter 1 ≤ m ≤ n2, it can preprocess P in time O(n6m1+δ), for any δ > O, into a data structure of size O(n6m1+δ), so that a query can be answered in time O((√n/m1/4) log n). If one query point always lies on an edge of P, the algorithm can be improved to use O(n5m1+δ) preprocessing time and storage and guarantee O((n/m)1/3 log n) query time for any choice of m between 1 and n.

    Original languageEnglish (US)
    Pages (from-to)1689-1713
    Number of pages25
    JournalSIAM Journal on Computing
    Volume26
    Issue number6
    DOIs
    StatePublished - Dec 1997

    Keywords

    • Convex polytopes
    • Geodesics
    • Shortest paths
    • Star unfolding

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Star unfolding of a polytope with applications'. Together they form a unique fingerprint.

    Cite this