Two-point L₁ shortest path queries in the plane

DOI10.1145/2582112.2582125zbMATH Open1395.68297arXiv1403.3458OpenAlexW2025376602MaRDI 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)

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$).

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

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

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)

Cited In (6)

• Shortest rectilinear path queries to rectangles in a rectangular domain
• ON GEOMETRIC PATH QUERY PROBLEMS
• An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains
• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• 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

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)