Citation
Mauch, Sean Patrick (2003) Efficient algorithms for solving static HamiltonJacobi equations. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd05202003170423
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 3D, including kdtrees, 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 singlesource, nonnegative weight, shortestpaths 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 HamiltonJacobi 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 shortestpaths algorithm discussed above can be used to develop an ordered, upwind, finite difference algorithm for solving static HamiltonJacobi 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.
Item Type:  Thesis (Dissertation (Ph.D.))  

Subject Keywords:  HamiltonJacobi equations  
Degree Grantor:  California Institute of Technology  
Division:  Engineering and Applied Science  
Major Option:  Applied And Computational Mathematics  
Thesis Availability:  Public (worldwide access)  
Research Advisor(s): 
 
Thesis Committee: 
 
Defense Date:  23 April 2003  
NonCaltech Author Email:  sean (AT) caltech.edu  
Funders: 
 
Record Number:  CaltechETD:etd05202003170423  
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd05202003170423  
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  1888  
Collection:  CaltechTHESIS  
Deposited By:  Imported from ETDdb  
Deposited On:  27 May 2003  
Last Modified:  26 Dec 2012 02:43 
Thesis Files

PDF (thesis.pdf)
 Final Version
See Usage Policy. 2928Kb 
Repository Staff Only: item control page