An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains
We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain D, consisting of n tetrahedra with positive weights, and a real number ε ∈ (0,1), our algorithm constructs paths in D from a fixed source vertex to all vertices of D, the costs of which are at most 1 + ε times the costs of (weighted) shortest paths, in O(C(D)n/ε2.5logn/εlog31/ε) time, where C(D) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25-53, 2005), to three dimensions.
|Keywords||Approximation algorithms, Shortest path problems, Voronoi diagrams, Weighted 3-d domains, Weighted paths|
|Journal||Discrete and Computational Geometry|
Aleksandrov, L. (Lyudmil), Djidjev, H. (Hristo), Maheshwari, A, & Sack, J.-R. (2013). An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains. Discrete and Computational Geometry, 50(1), 124–184. doi:10.1007/s00454-013-9486-0