2026-07-25T02:44:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10463 2024-03-06T10:46:03Z ddc:004 open_access

A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains Wang, Haitao shortest paths two-point queries L_1 metric polygonal domains Let P 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 P 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 * 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 log^3 h/log log h)) size in O(n+(h^2 log^4 h/log log h)) time such that each query can be answered in O(log n) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.59 urn:nbn:de:0030-drops-104631 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.59 eng https://creativecommons.org/licenses/by/3.0/legalcode