Querying approximate shortest paths in anisotropic regions - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Computing Année : 2010

Querying approximate shortest paths in anisotropic regions

Résumé

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let $rhogeqslant1$ be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric 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. Let $varepsilon$ be any number strictly between 0 and 1. Our data structure returns a $(1+varepsilon)$ approximation of the shortest path cost from the fixed source to a query destination in $O(logfrac{rho n}{varepsilon})$ time. Afterwards, a $(1+varepsilon)$-approximate shortest path can be reported in $O(log n)$ time plus the complexity of the path. The data structure uses $O(frac{rho^2n^3 {varepsilon^2}logfrac{rho n}{varepsilon})$ space and can be built in $O(frac{rho^2n^3}{varepsilon^2}(logfrac{rho n}{varepsilon})^2)$ time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang. Querying approximate shortest paths in anisotropic regions. SIAM Journal on Computing, 2010, 39 (5), pp.1888-1918. ⟨10.1137/080742166⟩. ⟨hal-02668390⟩

Collections

INRA INRAE MATHNUM
10 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More