Optimal shortest path and minimum-link path queries in the presence of obstacles

Yi Jen Chiang, Roberto Tamassia

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We present efficient algorithms for shortest-path and minimum-link- path queries between two convex polygons inside a simple polygon, which acts as an obstacle to be avoided. We also extend our results to the dynamic case, and give a unified data structure that supports both queries for convex polygons in the same region of a connected planar subdivision. Performing shortest-path queries is a variation of the well studied separation problem, which has not been efficiently solved before in the presence of obstacles. Also, it was not previously known how to perform minimum-link-path queries in a dynamic environment, even for two-point queries.

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA'94 - 2nd Annual European Symposium, Proceedings
    EditorsJan van Leeuwen
    PublisherSpringer Verlag
    Pages266-277
    Number of pages12
    ISBN (Print)9783540584346
    DOIs
    StatePublished - 1994
    Event2nd Annual European Symposium on Algorithms, ESA 1994 - Utrecht, Netherlands
    Duration: Sep 26 1994Sep 28 1994

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume855 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other2nd Annual European Symposium on Algorithms, ESA 1994
    CountryNetherlands
    CityUtrecht
    Period9/26/949/28/94

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Optimal shortest path and minimum-link path queries in the presence of obstacles'. Together they form a unique fingerprint.

  • Cite this

    Chiang, Y. J., & Tamassia, R. (1994). Optimal shortest path and minimum-link path queries in the presence of obstacles. In J. van Leeuwen (Ed.), Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings (pp. 266-277). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 855 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0049414