Approximate Shortest Paths in Anisotropic Regions

Abstract

Our goal is to find an approximate shortest path for a point robot moving in a planarsubdivision with n vertices. Let ae? 1 be a real number. Distances in each face of thissubdivision 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/ae.Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any " 2 (0, 1) and for any twopoints vs and vd, we give an algorithm that finds a path from vs to vd whose cost is at most (1 + ") times the optimal. Our algorithm runs in O i ae 2 log ae "2 n3 log \\Gamma aen " \\Delta j time. Thisbound 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 havebeen considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in [1, ae] [ {1}, the time bound of our algorithm improves to O i ae log ae " n3 log \\Gamma aen " \\Delta j.