Fast methods for computing all-to-all geodesic paths for the Eikonal equation.

摘要

This thesis presents the Geodesic Path-Switching algorithm, a method for solving an all-to-all shortest path problem in a continuous region. Given a domain and a metric, the goal is to compute the shortest geodesic path between a collection of points given in the domain. The metric can be thought of as a cost function defined at every point in space, and the actual paths and cost must be computed. For every pair of starting and end points, the path corresponds to the solution of the Eikonal equation for a wave starting at the source and ending at the end point.;The algorithm presented is a dynamic programming method. At its core, it exploits methods borrowed from discrete graph theory to compute the solution to our continuous problem. We find shortest paths in subproblems, then use those paths as segments of a different shortest path. This method can be used to find path lengths for the shortest path between multiple pairs of endpoints. The algorithm also produces the position of an approximate path.;The path length is the time it takes to traverse the path, according to a known, position dependent speed function. We place a simple rectangular mesh on the region, which provides a graph-like setting for the problem. We apply concepts of methods used to solve the all-to-all shortest path problem on a graph to our continuous setting.;Floyd's algorithm is a method for solving the shortest path problem on a graph. It compares currently known paths to new paths made by joining two paths, one each from our original endpoints to a third node. Upon completion of the algorithm, we have shortest path lengths and the actual shortest paths for every pair of nodes in the graph.;In the continuous setting, mesh points play a similar role as the nodes in the graph setting. They describe endpoints of paths, and they determine regions through which we describe potential new shortest paths. The cell boundaries describe edges. A significant difference between the graph problem and the continuous problem is the potential paths whose length we seek to minimize. On a graph, paths may be made only from existing edges on the graph. In the continuous region, paths may pass through any point in the region.;We present a method for minimizing patty that intersect some small subregion at some point. We construct contours of known path lengths to determine the length of shortest paths made by joining together two paths at some point within that subregion. The dynamic programming principle of Floyd's algorithm motivates our method for comparing paths in order to find the shortest path. We use the upwind update procedure from the Fast Marching method to calculate path lengths for a small region.;The Geodesic Path-Switching algorithm produces shortest path lengths for every pair of mesh points. The algorithm may be slightly modified as to record a predecessor edge for each pair of mesh points. This is the last edge visited prior to reaching the destination node of the shortest path. Upon completion of the algorithm, we use this information to work backward along the series of edges through which the shortest path passes.;At every stage in the algorithm, we have a current shortest path for each pair of mesh points. This is the shortest path we have located to that point in the algorithm. When we find a shorter path, we adopt this as our new shortest path. As a result, there are paths present at each step of Geodesic Path-Switching method. This provides alternate paths for problems which allow suboptimal paths.