Today I read a paper titled “An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains”
The abstract is:
We present the first polynomial time approximation algorithm for computing shortest paths in weighted three-dimensional domains
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