×

Approximate shortest paths in anisotropic regions. (English) Zbl 1187.68636

Summary: Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with \(n\) vertices. Let \(\rho\geqslant 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))\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI