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

Yi Jen Chiang, Franco P. Preparata, Roberto Tamassia

    Research output: Contribution to conferencePaper

    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(log3 n) (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(log3 n) time (amortized for vertex updates).

    Original languageEnglish (US)
    Pages44-53
    Number of pages10
    StatePublished - 1993
    EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
    Duration: Jan 25 1993Jan 27 1993

    Other

    OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
    CityAustin, TX, USA
    Period1/25/931/27/93

    ASJC Scopus subject areas

    • Engineering(all)

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

  • Cite this

    Chiang, Y. J., Preparata, F. P., & Tamassia, R. (1993). Unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. 44-53. Paper presented at Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, .