TY - GEN
T1 - Querying approximate shortest paths in anisotropic regions
AU - Cheng, Siu Wing
AU - Na, Hyeon Suk
AU - Vigneron, Antoine
AU - Wang, Yajun
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Computational geometry
KW - Data structures
KW - Shortest path
UR - https://openalex.org/W2043285556
UR - https://www.scopus.com/pages/publications/35348884208
U2 - 10.1145/1247069.1247082
DO - 10.1145/1247069.1247082
M3 - Conference Paper published in a book
SN - 1595937056
SN - 9781595937056
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 84
EP - 91
BT - Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
T2 - 23rd Annual Symposium on Computational Geometry, SCG'07
Y2 - 6 June 2007 through 8 June 2007
ER -