Optimal shortest path queries in a simple polygon (Q1823689): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: J. E. Hershberger / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Hans-Dietrich Hecker / rank
Normal rank
 

Revision as of 09:15, 20 February 2024

scientific article
Language Label Description Also known as
English
Optimal shortest path queries in a simple polygon
scientific article

    Statements

    Optimal shortest path queries in a simple polygon (English)
    0 references
    0 references
    1989
    0 references
    The paper focuses on a simple version of the Euclidean shortest path problem: moving a point inside a simple polygon with n sides. It shows how to preprocess the polygon P so that, given two query points p and q inside the polygon, the Euclidean length of the shortest path inside P from p to q can be found in sublinear time 0(log n). The path itself must be polygonal. The paper gives a data structure that supports such shortest path queries when both endpoints are part of the query. The preprocessing phase gives a hierarchy of nested subpolygons over an underlying triangulation, such that any shortest path crosses a small number of subpolygons only. So preprocessing consists of triangulation plus a linear amount of additional work. Interesting applications and extensions are discussed at the end of the paper (disk moving, relative convex hulls).
    0 references
    computational geometry
    0 references
    simple polygons
    0 references
    shortest path moving
    0 references

    Identifiers