Querying approximate shortest paths in anisotropic regions - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement
Processing math: 100%
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(logfracrhonvarepsilon) time. Afterwards, a (1+varepsilon)-approximate shortest path can be reported in O(logn) time plus the complexity of the path. The data structure uses $O(frac{rho^2n^3 {varepsilon^2}logfrac{rho n}{varepsilon})spaceandcanbebuiltinO(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
22 Consultations
0 Téléchargements

Altmetric

Partager

More