License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10463/
Go to the corresponding LIPIcs Volume Portal

Wang, Haitao

A Divide-and-Conquer Algorithm for Two-Point L_1 Shortest Path Queries in Polygonal Domains

pdf-format:
LIPIcs-SoCG-2019-59.pdf (0.6 MB)

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
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI