HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6556
Title: Querying approximate shortest paths in anisotropic regions
Authors: Cheng, Siu-Wing
Na, Hyeon-Suk
Vigneron, Antoine
Wang, Yajun
Keywords: Shortest path
Anisotropic regions
Convex distance functions
Approximation algorithms
Issue Date: 2008
Citation: SIAM journal on computing, v. 39, no. 5, p. 1888-1918
Abstract: We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let ρ ≥ 1 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/ρ. Different convex distance functions may be used for different faces, and obstacles are allowed. Let ε be any number strictly between 0 and 1. Our data structure returns a (1+ε) approximation of the shortest path cost from the fixed source to a query destination in O(log ρn/ε ) time. Afterwards, a (1+ε)-approximate shortest path can be reported in O(log n) time plus the complexity of the path. The data structure uses O( ρ2n32 log ρn/ε ) space and can be built in O( ρ2n32 (log ρn/ε )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.
Rights: Copyright © SIAM. This paper is made available with permission of the Society for Industrial and Applied Mathematics for limited noncommerical distribution only.
URI: http://hdl.handle.net/1783.1/6556
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
querying.pdf384KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.