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


    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
    Number of pages12
    ISBN (Print)9783540584346
    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


    Other2nd Annual European Symposium on Algorithms, ESA 1994

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    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