2011/02/15 by Aleksandrov, Lyudmil, Djidjev, Hristo, Maheshwari, Anil +1
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graphics (cs.GR) #Robotics (cs.RO)
paper · doi:10.48550/arxiv.1102.3165
We present the first polynomial time 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 \eps∈(0,1), our algorithm constructs paths in \D from a fixed source vertex to all vertices of \D, whose costs are at most 1+\eps times the costs of (weighted) shortest paths, in O(\C(\D)\fracn\eps2.5log(n)/(\eps)log3(1)/(\eps)) 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, Maheshwari and Sack [JACM 2005] to three dimensions.