@inproceedings{05a78fe3dcf94210aaa79d5641b1d657,

title = "Querying approximate shortest paths in anisotropic regions",

abstract = "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(logn/) 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.",

keywords = "Computational geometry, Data structures, Shortest path",

author = "Cheng, {Siu Wing} and Na, {Hyeon Suk} and Antoine Vigneron and Yajun Wang",

year = "2007",

month = oct,

day = "22",

doi = "10.1145/1247069.1247082",

language = "English (US)",

isbn = "1595937056",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "84--91",

booktitle = "Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07",

note = "23rd Annual Symposium on Computational Geometry, SCG'07 ; Conference date: 06-06-2007 Through 08-06-2007",

}