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

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 2 users not shown)
Property / author
 
Property / author: J. E. Hershberger / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Hans-Dietrich Hecker / rank
Normal rank
 
Property / author
 
Property / author: J. E. Hershberger / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Hans-Dietrich Hecker / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric applications of a matrix-searching algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Point Location in a Monotone Subdivision / rank
 
Normal rank
Property / cites work
 
Property / cites work: Euclidean shortest paths in the presence of rectilinear barriers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maintenance of configurations in the plane / rank
 
Normal rank
Property / cites work
 
Property / cites work: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon / rank
 
Normal rank

Latest revision as of 10:45, 20 June 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
    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
    0 references
    computational geometry
    0 references
    simple polygons
    0 references
    shortest path moving
    0 references