August 2nd, 2001

Marching on Triangulated Domains

Ron Kimmel
CS Dept. Technion, Haifa 32000, Israel

The speaker will review a computationally optimal numerical answer to the question of how to compute the shortest path between two points on a surface, also known as the `minimal geodesic problem'. We (Kimmel-Sethian) have extended a numerical technique for solving Eikonal equations on flat domains to triangulated curved domains. It provides a scheme for computing geodesic distances and thereby solving the minimal geodesic problem. Next, we show who to use the method to compute Voronoi diagrams and offset curves on surfaces. We also present applications of the technique to areas like 3D shape reconstruction in computer vision, path planning in robotic navigation, and texture mapping in computer graphics.