Share Email Print

Proceedings Paper

Finding shortest paths on surfaces by fast global approximation and precise local refinement
Author(s): Ron Kimmel; Nahum Kiryati
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Finding the shortest path between points on a surface is a challenging global optimization problem. It is difficult to devise an algorithm that is computationally efficient, locally accurate and guarantees to converge to the globally shortest path. In this paper a two stage coarse to the fine approach of finding shortest paths is suggested. In the first stage a fast algorithm is used to obtain an approximation to the globally shortest path. In the second stage the approximation is refined into a locally optimal path. In the first stage we use the fast algorithm introduced by Kiryati and Szekely that combines a 3-D length estimator with graph search. This path is then refined to a shorter geodesic curve by an algorithm that deforms an arbitrary initial curve ending at two given surface points via geodesic curvature shortening flow. The 3D curve shortening flow is transformed into an equivalent 2D one that is implemented using an efficient numerical algorithm for curve evolution with fixed end points, introduced by Kimmel and Sapiro.

Paper Details

Date Published: 4 January 1995
PDF: 12 pages
Proc. SPIE 2356, Vision Geometry III, (4 January 1995); doi: 10.1117/12.198608
Show Author Affiliations
Ron Kimmel, Technion--Israel Institute of Technology (Israel)
Nahum Kiryati, Technion--Israel Institute of Technology (Israel)

Published in SPIE Proceedings Vol. 2356:
Vision Geometry III
Robert A. Melter; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?