Approximate Shortest Paths in Anisotropic Regions

摘要

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let $\rho\geq 1$ be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any $\varepsilon\in(0,1)$ and for any two points $v_s$ and $v_d$, we give an algorithm that finds a path from $v_s$ to $v_d$ whose cost is at most $(1+\varepsilon)$ times the optimal. Our algorithm runs in $O(\frac{\rho^2\log \rho}{\varepsilon^2}n^3 \log(\frac{\rho n}\varepsilon))$ time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in $[1,\rho]\cup \{\infty\}$, the time bound of our algorithm improves to $O(\frac{\rho\log \rho}{\varepsilon}n^3 \log(\frac{\rho n}\varepsilon))$.