|
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( ρ2n3/ε2 log ρn/ε ) space and can be built in O( ρ2n3/ε2 (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 |
Size | Format |
|---|
| querying.pdf | | 384Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
