Shortest path problems on polyhedral surfaces.

摘要

Shortest path algorithms have been studied for many years, as they have applications in many areas of computer science. Recently, much of the research has been geared towards computing approximations of shortest paths in order to reduce the large time complexities which are inherent to exact solutions. In some instances, approximation algorithms may provide the only solution since there may be no existing algorithm that produces an exact solution.; In this work, we develop several algorithms for computing approximations of weighted shortest paths on polyhedral surfaces. Our techniques are mainly based on discretizing the polyhedron in order to reduce the problem to a graph shortest path problem. We give several schemes which differ in the way in which the polyhedron is discretized. The schemes are based on adding Steiner points to faces of the polyhedron, creating a graph by interconnecting these points and then searching this graph for a solution. We show through experimental evaluation that these techniques are practical.; All of our algorithms allow a tradeoff between accuracy and running time. We provide ε-approximation algorithms that improve upon previous work in terms of n (the number of faces of the polyhedron). In addition to Euclidean and weighted metrics, we also give algorithms for computing shortest anisotropic paths. Lastly, we show how these algorithms can be implemented in parallel. Through implementation, we show that our parallel algorithm achieves up to 64% efficiency.