A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains

DOI10.20382/JOCG.V11I1A10MaRDI QIDQ5120154zbMATH OpenOpenAlexFDO

Authors Haitao Wang

Publication date 9 September 2020

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

Mathematics Subject Classification ID

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

Abstract: Let $mathcalP$ be a polygonal domain of $h$ holes and $n$ vertices. We study the problem of constructing a data structure that can compute a shortest path between $s$ and $t$ in $mathcalP$ under the $L_1$ metric for any two query points $s$ and $t$. To do so, a standard approach is to first find a set of $n_s$ "gateways" for $s$ and a set of $n_t$ "gateways" for $t$ such that there exist a shortest $s$-$t$ path containing a gateway of $s$ and a gateway of $t$, and then compute a shortest $s$-$t$ path using these gateways. Previous algorithms all take quadratic $O(n_{s}cdot{n}_t)$ time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in $O(n_s+n_{t}log{n}_s)$ time. As a consequence, we construct a data structure of $O(n+(h^{2}lo{g}^{3}h/loglogh))$ size in $O(n+(h^{2}lo{g}^{4}h/loglogh))$ time such that each query can be answered in $O(logn)$ time.

Recommendations

• A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
• Querying two boundary points for shortest paths in a polygonal domain (extended abstract)
• \(L_{1}\) shortest path queries in simple polygons
• Two-point \(L_1\) shortest path queries in the plane
• Two-point L₁ shortest path queries in the plane
• Shortest Path Queries in Polygonal Domains
• Querying two boundary points for shortest paths in a polygonal domain
• L₁ shortest path queries among polygonal obstacles in the plane
• Optimal shortest path queries in a simple polygon
• A new data structure for shortest path queries in a simple polygon

Cited in

(5)

• A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
• Towards space efficient two-point shortest path queries in a polygonal domain
• A new algorithm for Euclidean shortest paths in the plane
• Link diameter, radius and 2-point link distance queries in polygonal domains
• Towards space efficient two-point shortest path queries in a polygonal domain

This page was built for publication: A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains

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