Skip to main content
Journal cover image

Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces

Publication ,  Journal Article
Mémoli, F; Sapiro, G
Published in: Journal of Computational Physics
November 1, 2001

An algorithm for the computationally optimal construction of intrinsic weighted distance functions on implicit hyper-surfaces is introduced in this paper. The basic idea is to approximate the intrinsic weighted distance by the Euclidean weighted distance computed in a band surrounding the implicit hyper-surface in the embedding space, thereby performing all the computations in a Cartesian grid with classical and efficient numerics. Based on work on geodesics on Riemannian manifolds with boundaries, we bound the error between the two distance functions. We show that this error is of the same order as the theoretical numerical error in computationally optimal, Hamilton-Jacobi-based, algorithms for computing distance functions in Cartesian grids. Therefore, we can use these algorithms, modified to deal with spaces with boundaries, and obtain also for the case of intrinsic distance functions on implicit hyper-surfaces a computationally efficient technique. The approach can be extended to solve a more general class of Hamilton-Jacobi equations defined on the implicit surface, following the same idea of approximating their solutions by the solutions in the embedding Euclidean space. The framework here introduced thereby allows for the computations to be performed on a Cartesian grid with computationally optimal algorithms, in spite of the fact that the distance and Hamilton-Jacobi equations are intrinsic to the implicit hyper-surface. © 2001 Academic Press.

Duke Scholars

Published In

Journal of Computational Physics

DOI

ISSN

0021-9991

Publication Date

November 1, 2001

Volume

173

Issue

2

Start / End Page

730 / 764

Related Subject Headings

  • Applied Mathematics
  • 51 Physical sciences
  • 49 Mathematical sciences
  • 40 Engineering
  • 09 Engineering
  • 02 Physical Sciences
  • 01 Mathematical Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Mémoli, F., & Sapiro, G. (2001). Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. Journal of Computational Physics, 173(2), 730–764. https://doi.org/10.1006/jcph.2001.6910
Mémoli, F., and G. Sapiro. “Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces.” Journal of Computational Physics 173, no. 2 (November 1, 2001): 730–64. https://doi.org/10.1006/jcph.2001.6910.
Mémoli F, Sapiro G. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. Journal of Computational Physics. 2001 Nov 1;173(2):730–64.
Mémoli, F., and G. Sapiro. “Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces.” Journal of Computational Physics, vol. 173, no. 2, Nov. 2001, pp. 730–64. Scopus, doi:10.1006/jcph.2001.6910.
Mémoli F, Sapiro G. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. Journal of Computational Physics. 2001 Nov 1;173(2):730–764.
Journal cover image

Published In

Journal of Computational Physics

DOI

ISSN

0021-9991

Publication Date

November 1, 2001

Volume

173

Issue

2

Start / End Page

730 / 764

Related Subject Headings

  • Applied Mathematics
  • 51 Physical sciences
  • 49 Mathematical sciences
  • 40 Engineering
  • 09 Engineering
  • 02 Physical Sciences
  • 01 Mathematical Sciences