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 , consisting of tetrahedra with positive weights, and a real number , our algorithm constructs paths in from a fixed source vertex to all vertices of , the costs of which are at most times the costs of (weighted) shortest paths, in time, where 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.
approximation algorithms weighted 3-d domains voronoi diagrams shortest path problems weighted paths