Approximate shortest paths in anisotropic regions - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement
Article Dans Une Revue SIAM Journal on Computing Année : 2008

Approximate shortest paths in anisotropic regions

Résumé

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let ρ ≥ 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/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For all ε ∈ (0, 1), and for any two points vs and vd, we give an algorithm that finds a path from vs to vd whose cost is at most (1 + ε) times the minimum cost. Our algorithm runs in O (ρ2logρ/ε2n3 log (ρn/ε)) 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, ρ] ∪ {∞}, the time bound of our algorithm improves to O (ρ2logρ/εn3 log (ρn/ε))

Dates et versions

hal-02666491 , version 1 (31-05-2020)

Identifiants

Citer

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang. Approximate shortest paths in anisotropic regions. SIAM Journal on Computing, 2008, 38 (3), pp.802-824. ⟨10.1137/06067777X⟩. ⟨hal-02666491⟩

Collections

INRA INRAE MATHNUM
27 Consultations
0 Téléchargements

Altmetric

Partager

More