Computer Science – Computational Geometry
Scientific paper
2012-02-26
Computer Science
Computational Geometry
48 pages; 19 figures; partial results appeared in ESA 2011
Scientific paper
Given a point $s$ and a set of $h$ pairwise disjoint polygonal obstacles of totally $n$ vertices in the plane, we present a new algorithm for building an $L_1$ shortest path map of size O(n) in $O(T)$ time and O(n) space 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 shortest path can be found in additional time proportional to the number of edges of the path, where $T$ is the time for triangulating the free space. It is currently known that $T=O(n+h\log^{1+\epsilon}h)$ for an arbitrarily small constant $\epsilon>0$. If the triangulation can be done optimally (i.e., $T=O(n+h\log h)$), then our algorithm is optimal. Previously, the best algorithm computes such an $L_1$ shortest path map in $O(n\log n)$ time and O(n) space. Our techniques can be extended to obtain improved results for other related problems, e.g., computing the $L_1$ geodesic Voronoi diagram for a set of point sites in a polygonal domain, finding shortest paths with fixed orientations, finding approximate Euclidean shortest paths, etc.
Chen Danny Z.
Wang Haitao
No associations
LandOfFree
Computing L1 Shortest Paths among Polygonal Obstacles in the Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing L1 Shortest Paths among Polygonal Obstacles in the Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing L1 Shortest Paths among Polygonal Obstacles in the Plane will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-215586