Efficient algorithms for solving static Hamilton -Jacobi equations.

摘要

We present an algorithm for computing the closest point, transform to an explicitly described manifold on a rectilinear grid in low dimensional spaces. The closest point transform finds the closest point on a manifold and the Euclidean distance to a manifold for the points in a grid. We consider manifolds composed of simple geometric shapes, such as, a set of points, piecewise linear curves or triangle meshes. The algorithm solves the eikonal equation |∇u| = 1 with the method of characteristics. For many problems, the computational complexity of the algorithm is linear in both the number of grid points and the complexity of the manifold.;Many query problems can be aided by using orthogonal range queries (ORQ). There are several standard data structures for performing ORQ's in 3-D, including kd-trees, octrees, and cell arrays. We develop additional data structures based on cell arrays. We study the characteristics of each data structure and compare their performance.;We present a new algorithm for solving the single-source, non-negative weight, shortest-paths problem. Dijkstra's algorithm solves this problem with computational complexity O ((E + V)log V) where E is the number of edges and V is the number of vertices. The new algorithm, called Marching with a Correctness Criterion (MCC), has computational complexity O (E + RV), where R is the ratio of the largest to smallest edge weight.;Sethian's Fast Marching Method (FMM) may be used to solve static Hamilton-Jacobi equations. It has computational complexity O (N log N), where N is the number of grid points. The FMM has been regarded as an optimal algorithm because it is closely related to Dijkstra's algorithm. The new shortest-paths algorithm discussed above can be used to develop an ordered, upwind, finite difference algorithm for solving static Hamilton-Jacobi equations. This algorithm requires difference schemes that difference not only in coordinate directions, but in diagonal directions as well. It has computational complexity O(RN), where R is the ratio of the largest to smallest propagation speed and N is the number of grid points.