Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces
2001-04
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces
Authors
Published Date
2001-04
Publisher
Type
Abstract
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 computationally optimal 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 optimal 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 to perform the computations 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. For other surface representations like triangulated or unorganized points ones, the algorithm here introduced can be used after simple pre-processing of the data.
Keywords
Description
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Memoli, Facundo; Sapiro, Guillermo. (2001). Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/3556.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.