LIPIcs.STACS.2013.293.pdf
- Filesize: 0.6 MB
- 12 pages
Document
L_1 Shortest Path Queries among Polygonal Obstacles in the Plane
Authors
-
Part of:
Volume:
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2013-02-26
Cite AsGet BibTex
Danny Z. Chen and Haitao Wang. L_1 Shortest Path Queries among Polygonal Obstacles in the Plane. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 293-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.293
https://doi.org/10.4230/LIPIcs.STACS.2013.293
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.
Keywords
- computational geometry
- shortest path queries
- shortest paths among obstacles
- $L_1$/$L_infty$/rectilinear metric
- shortest path maps
- geodesic Vorono
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads