THESIS
2008
x, 103 leaves : ill. ; 30 cm
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.
^{2} ^{3} ^{2}...[
Read more ]
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 Ο(ρ
^{2}n
^{3}log ρ/ε
^{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(ρ
^{2}n
^{3}/ε
^{2}(log*ρn/ε)
^{2}), and the space complexity of the data structure is O(ρ
^{2}n
^{3}/ε
^{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.
Post a Comment