HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >
Please use this identifier to cite or link to this item:
|Title: ||Path problems in anisotropic regions|
|Authors: ||Wang, Yajun|
|Issue Date: ||2008 |
|Abstract: ||We investigate the approximate shortest path problems in anisotropic regions in the plane. The anisotropic regions are defined by a triangulation with n vertices. Let ρ ≥ 1 be a real number. Distances in each face of this triangulation are measured by a 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. These convex distance functions may be asymmetric.
For all ε ∈ (0,1), and for any two points s and t, we give an algorithm that finds a path from s to t whose cost is at most (1 + ε) times the optimal. Our algorithm runs in Ο(ρ2n3log ρ/ε2*log(ρn/ε)) time. For any fixed vertex s of the triangulation and ε ∈ (0,1), we develop a data structure to answer (1 + ε)-approximate shortest path queries for any point t in the triangulation in O(log*ρn/ε) time. The preprocessing takes time O(ρ2n3/ε2(log*ρn/ε)2), and the space complexity of the data structure is O(ρ2n3/ε2*log*ρn/ε). The complexity of the data structure matches the bound for the approximate shortest path algorithm up to a logarithmic factor.
Unlike most related previous work, our time and space bounds do not depend on the geometry of the environment; in particular they do not depend on the minimum angle in the triangulation.|
|Description: ||Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008|
x, 103 leaves : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2008 WangY
|Appears in Collections:||CSE Doctoral Theses|
Files in This Item:
All items in this Repository are protected by copyright, with all rights reserved.