Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3469

Path problems in anisotropic regions

Authors Wang, Yajun
Issue Date 2008
Summary 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.
Note Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 343 B HTML