An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

Lyudmil Aleksandrov, Hristo Djidjev, Anil Maheshwari +1

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$ t…