Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Dissertation
Author	Mauch, Sean Patrick
Author's Email Address	sean AT caltech.edu
URN	etd-05202003-170423
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-05202003-170423
Title	Efficient algorithms for solving static Hamilton-Jacobi equations
Degree	PhD
Option	Applied Mathematics
Advisory Committee	Advisor Name Title Dan Meiron Committee Chair K. Mani Chandy Committee Member Peter Schroder Committee Member Tom Hou Committee Member
Keywords	Hamilton-Jacobi equations
Date of Defense	2003-04-23
Availability	unrestricted
Abstract 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 |grad 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 + R V), 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(R N), where R is the ratio of the largest to smallest propagation speed and N is the number of grid points.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    thesis.pdf 3.00 Mb 00:13:53 00:07:08 00:06:14 00:03:07 00:00:15