Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Chen, Danny Z.; Wang, Haitao https://www.dagstuhl.de/lipics License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-39425
URL:

;

L_1 Shortest Path Queries among Polygonal Obstacles in the Plane

pdf-format:


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
Seminar: 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