A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps

Y. I Jen Chiang, Franco P. Preparata, Roberto Tamassia

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map M with n vertices and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, and shortest-path queries in M. The space requirement is O (n log n). Point-location queries take time O (log n). Ray-shooting and shortest-path queries take time O (log3n) (plus O(k) time if the k edges of the shortest path are reported in addition to its length). Updates consist of insertions and deletions of vertices and edges, and take O(log3n) time (amortized for vertex updates). This is the first polylog-time dynamic data structure for shortest-path and ray-shooting queries. It is also the first dynamic point-location data structure for connected planar maps that achieves optimal query time.

    Original languageEnglish (US)
    Pages (from-to)207-233
    Number of pages27
    JournalSIAM Journal on Computing
    Volume25
    Issue number1
    DOIs
    StatePublished - Feb 1996

    Keywords

    • Computational geometry
    • Dynamic algorithm
    • Point location
    • Ray shooting
    • Shortest path

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics

    Fingerprint

    Dive into the research topics of 'A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps'. Together they form a unique fingerprint.

    Cite this