xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40"> Abstract

Computing Geodesic Distances on Triangular Meshes

Marcin Novotni and Reinhard Klein
University of Bonn
Institut für Informatik II.
Tel.: +49 228734122 Fax.: +49 228734212
D-53117 Bonn
Germany

e-mail(s): {marcin,rk}@cs.uni-bonn.de

http://cg.cs.uni-bonn.de

Keywords: geodesic distances, computational geometry

Abstract

We present an approximation method to compute geodesic distances on triangulated domains in the three dimensional space. Our particular approach is based on the Fast Marching Method for solving the Eikonal equation on triangular meshes. As such, the algorithm is a wavefront propagation method, a reminiscent of the Dijkstra algorithm, which runs in O(n log n) steps.

 

Last update: 08.05.2001