Two-point L₁ shortest path queries in the plane

DOI10.1145/2582112.2582125MaRDI QIDQ4635565zbMATH OpenOpenAlexFDO

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

\(L_1\) metricpolygonal domainspolygons with holesshortest pathstwo-point queriesweighted rectilinear obstacles

Mathematics Subject Classification ID

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

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₁ shortest path queries in the plane
• L₁ 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

(12)

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

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)