Computing $$L_1$$ Shortest Paths Among Polygonal Obstacles in the Plane

摘要

Given a point $s$ and a set of $h$ pairwise disjoint polygonal obstacles oftotally $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 thatfor any query point $t$, the length of the $L_1$ shortest obstacle-avoidingpath from $s$ to $t$ can be reported in $O(log n)$ time and the actualshortest path can be found in additional time proportional to the number ofedges of the path, where $T$ is the time for triangulating the free space. Itis currently known that $T=O(n+hlog^{1+epsilon}h)$ for an arbitrarily smallconstant $epsilon>0$. If the triangulation can be done optimally (i.e.,$T=O(n+hlog h)$), then our algorithm is optimal. Previously, the bestalgorithm computes such an $L_1$ shortest path map in $O(nlog n)$ time andO(n) space. Our techniques can be extended to obtain improved results for otherrelated problems, e.g., computing the $L_1$ geodesic Voronoi diagram for a setof point sites in a polygonal domain, finding shortest paths with fixedorientations, finding approximate Euclidean shortest paths, etc.