L₁ shortest path queries in simple polygons

DOI10.1016/J.TCS.2019.04.023MaRDI QIDQ2272388zbMATH OpenOpenAlexWikidataFDO

Authors Sang Won Bae, Haitao Wang

Publication date 10 September 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.07481

zbMATH Keywords

\(L_1\) metricmountain decompositionsshortest pathssimple polygonstwo-point queries

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Let $P$ be a simple polygon of $n$ vertices. We consider two-point $L_1$ shortest path queries in $P$. We build a data structure of $O(n)$ size in $O(n)$ time such that given any two query points $s$ and $t$, the length of an $L_1$ shortest path from $s$ to $t$ in $P$ can be computed in $O(logn)$ time, or in $O(1)$ time if both $s$ and $t$ are vertices of $P$, and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.

Recommendations

• L₁ shortest path queries among polygonal obstacles in the plane
• Two-point \(L_1\) shortest path queries in the plane
• Two-point L₁ shortest path queries in the plane
• scientific article; zbMATH DE number 512835
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane

Cites work

• \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• Computing minimum length paths of a given homotopy class
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Fast Algorithms for Finding Nearest Common Ancestors
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Matrix Searching with the Shortest-Path Metric
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Optimal shortest path queries in a simple polygon
• The level ancestor problem simplified
• Triangulating a simple polygon in linear time
• Two-point L₁ shortest path queries in the plane

Cited in

(9)

• A new data structure for shortest path queries in a simple polygon
• Optimal shortest path queries in a simple polygon
• scientific article; zbMATH DE number 512835 (Why is no real title available?)
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• scientific article; zbMATH DE number 742973 (Why is no real title available?)
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• A new algorithm for Euclidean shortest paths in the plane

This page was built for publication: \(L_{1}\) shortest path queries in simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272388)