Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Querying approximate shortest paths in anisotropic regions

Abstract : 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.
Type de document :
Article dans une revue
Liste complète des métadonnées
Déposant : Migration Prodinra <>
Soumis le : dimanche 31 mai 2020 - 12:43:45
Dernière modification le : vendredi 12 juin 2020 - 10:43:26




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



Consultations de la notice