HKUST Library Institutional Repository Banner

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:

File Description SizeFormat

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