Optimal shortest path queries in a simple polygon (Q1823689): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
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 | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0022-0000(89)90041-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2038699153 / rank | |||
Normal rank |
Latest revision as of 11:16, 30 July 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
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