A Caltech Library Service

Efficient Algorithms for Solving Static Hamilton-Jacobi Equations


Mauch, Sean Patrick (2003) Efficient Algorithms for Solving Static Hamilton-Jacobi Equations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/5R5P-Y603.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Hamilton-Jacobi 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):
  • Meiron, Daniel I.
Thesis Committee:
  • Meiron, Daniel I. (chair)
  • Chandy, K. Mani
  • Schroeder, Peter
  • Hou, Thomas Y.
Defense Date:23 April 2003
Funding AgencyGrant Number
Accelerated Strategic Computing InitiativeB341492
Record Number:CaltechETD:etd-05202003-170423
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1888
Deposited By: Imported from ETD-db
Deposited On:27 May 2003
Last Modified:13 May 2021 21:10

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page