Two-point Euclidean shortest path queries in the plane

Yi Jen Chiang, Joseph S.B. Mitchell

    Research output: Contribution to conferencePaperpeer-review


    We consider the two-point query version of the fundamental geometric shortest path problem: Given a set h of polygonal obstacles in the plane, having a total of n vertices, build a data structure such that for any two query points s and t we can efficiently determine the length, d(s,t), of an Euclidean shortest obstacle-avoiding path, π(s, t), from s to t. Additionally, our data structure should allow one to report the path π(s, t), in time proportional to its (combinatorial) size. We present various methods for solving this two-point query problem, including algorithms with o(n), O(log n+h), O(h log n), O(log2 n) or optimal O(log n) query times, using polynomial-space data structures, with various tradeoffs between space and query time. While several results have been known for approximate two-point Euclidean shortest path queries, it has been a well-publicized open problem to obtain sublinear query time for the exact version of the problem. Our methods also yield data structures for two-point shortest path queries on nonconvex polyhedral surfaces.

    Original languageEnglish (US)
    Number of pages10
    StatePublished - 1999
    EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
    Duration: Jan 17 1999Jan 19 1999


    OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
    CityBaltimore, MD, USA

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'Two-point Euclidean shortest path queries in the plane'. Together they form a unique fingerprint.

    Cite this