An Efficient Parallel Solution for Euclidean Shortest Paths in Three Dimensions

We describe an efficient parallel solution for the problem of finding the shortest Euclidean path between two points in three dimensional space in the presence of polyhedral obstacles. We consider the important case where the order in which the obstacles are encountered in this shortest path is known. In particu-lar for this case we describe an efficient parallel numerical iterative method on a--------ooneurrent-read-exclusive·write-synchronous-share~emmy_modet--'PhlOeciiinte"laa-~-----------dons are essentially convergent non-linear block Gauss-Seidel. For special rela-tive orientations of the, say n, JX)lyhedral obstacles, we further describe a direct method that gives the exact solution in 0 (log n) time using n processors