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
Communication Dans Un Congrès Année : 2007

Querying approximate shortest paths in anisotropic regions

Résumé

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let ρ ≥ 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/ρ. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let ε be any number strictly between 0and 1. Our data structure returns a (1+ε)approximation of the shortest path cost from the fixed source to a querydestination in O(logρn/ε) time. Afterwards, a(1+ε)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O(ρ2 n4/ε2 log ρn/ε) space and can be built in O((ρ2 n4)/(ε2)(log ρn/ε)2) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle.
Fichier non déposé

Dates et versions

hal-02750642 , version 1 (03-06-2020)

Identifiants

Citer

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang. Querying approximate shortest paths in anisotropic regions. Twenty-third Annual Symposium on Computational Geometry, Jun 2007, Gyeongju, South Korea. ⟨10.1145/1247069.1247082⟩. ⟨hal-02750642⟩

Collections

INRA INRAE MATHNUM
3 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More