O(N) Implementation of the Fast Marching Algorithm

Abstract

In this note we present an implementation of the fast marching algorithm for solving Eikonal equations that reduces the original run-time from O(N logN) to linear. This lower run-time cost is obtained while keeping an error bound of the same order of magnitude as the original algorithm. This improvement is achieved introducing the straight forward untidy priority queue, obtained via a quantization of the priorities in the marching computation. We present the underlying framework, estimations on the error, and examples showing the usefulness of the proposed approach.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 2005
Accession Number
ADA524974

Entities

People

  • Alberto Bartesaghi
  • Guillermo Sapiro
  • Liron Yatziv

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Arrays
  • Computational Complexity
  • Computational Fluid Dynamics
  • Computations
  • Engineering
  • Equations
  • Errors
  • Geospatial Intelligence
  • Information Operations
  • Linear Arrays
  • Mathematics
  • Military Research
  • Minnesota
  • Statistics
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Parallel and Distributed Computing.