Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.59
URN: urn:nbn:de:0030-drops-104631
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10463/
Wang, Haitao
A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{wang:LIPIcs:2019:10463,
author = {Haitao Wang},
title = {{A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {59:1--59:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10463},
URN = {urn:nbn:de:0030-drops-104631},
doi = {10.4230/LIPIcs.SoCG.2019.59},
annote = {Keywords: shortest paths, two-point queries, L_1 metric, polygonal domains}
}
| Keywords: | shortest paths, two-point queries, L_1 metric, polygonal domains | |
| Seminar: | 35th International Symposium on Computational Geometry (SoCG 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 11.06.2019 |
