Two-point L₁ shortest path queries in the plane

DOI10.1145/2582112.2582125zbMATH Open1395.68297OpenAlexW2025376602MaRDI QIDQ4635565FDOQ4635565

Authors Danny Z. Chen, Rajasekhar Inkulu, Haitao Wang 

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathspolygonal domainspolygons with holes\(L_1\) metrictwo-point queriesweighted rectilinear obstacles

Mathematics Subject Classification ID

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

Abstract: Let $mathcalP$ be a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices in the plane. We consider the problem of building a data structure that can quickly compute an $L_1$ shortest obstacle-avoiding path between any two query points $s$ and $t$. Previously, a data structure of size $O(n^{2}logn)$ was constructed in $O(n^{2}lo{g}^{2}n)$ time that answers each two-point query in $O(lo{g}^{2}n+k)$ time, i.e., the shortest path length is reported in $O(lo{g}^{2}n)$ time and an actual path is reported in additional $O(k)$ time, where $k$ is the number of edges of the output path. In this paper, we build a new data structure of size $O(n+h^{2}cdotloghcdot{4}^{sqrtlogh})$ in $O(n+h^{2}cdotlo{g}^{2}hcdot{4}^{sqrtlogh})$ time that answers each query in $O(logn+k)$ time. Note that $n+h^{2}cdotlo{g}^{2}hcdot{4}^{sqrtlogh}=O(n+h^{2+epsilon})$ for any constant $epsilon>0$. Further, we extend our techniques to the weighted rectilinear version in which the "obstacles" of $mathcalP$ are rectilinear regions with "weights" and allow $L_1$ paths to travel through them with weighted costs. Our algorithm answers each query in $O(logn+k)$ time with a data structure of size $O(n^{2}cdotlogncdot{4}^{sqrtlogn})$ that is built in $O(n^{2}cdotlo{g}^{2}ncdot{4}^{sqrtlogn})$ time (note that $n^{2}cdotlo{g}^{2}ncdot{4}^{sqrtlogn}=O(n^{2+epsilon})$ for any constant $epsilon>0$).

Recommendations

• Two-point \(L_1\) shortest path queries in the plane
• \(L_1\) shortest path queries among polygonal obstacles in the plane
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane

Cited in

(10)

• Shortest rectilinear path queries to rectangles in a rectangular domain
• ON GEOMETRIC PATH QUERY PROBLEMS
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• \(L_1\) shortest path queries among polygonal obstacles in the plane
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
• Two-point \(L_1\) shortest path queries in the plane
• \(L_{1}\) shortest path queries in simple polygons
• On geometric path query problems

This page was built for publication: Two-point \(L_1\) shortest path queries in the plane

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