License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.293
URN: urn:nbn:de:0030-drops-39425
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3942/
Go to the corresponding LIPIcs Volume Portal

Chen, Danny Z. ; Wang, Haitao

L_1 Shortest Path Queries among Polygonal Obstacles in the Plane

pdf-format:
30.pdf (0.6 MB)

Abstract

Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, after the free space is triangulated, we present an O(n+h log h) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of the L_1 shortest obstacle-avoiding path from s to t can be reported in O(log n) time and the actual path can be found in additional time proportional to the number of edges of the path. Previously, the best algorithm computes such a shortest path map in O(n log n) time and O(n) space. In addition, our techniques also yield an improved algorithm for computing the L_1 geodesic Voronoi diagram of m point sites among the obstacles.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2013:3942,
  author =	{Danny Z. Chen and Haitao Wang},
  title =	{{L_1 Shortest Path Queries among Polygonal Obstacles in the Plane}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{293--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3942},
  URN =		{urn:nbn:de:0030-drops-39425},
  doi =		{10.4230/LIPIcs.STACS.2013.293},
  annote =	{Keywords: computational geometry, shortest path queries, shortest paths among obstacles, $L_1$/$L_infty$/rectilinear metric, shortest path maps, geodesic Vorono}
}

Keywords: computational geometry, shortest path queries, shortest paths among obstacles, $L_1$/$L_infty$/rectilinear metric, shortest path maps, geodesic Vorono
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

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