Finding shortest paths on surfaces by fast global approximation and precise local refinement

Ron Kimmel; Nahum Kiryati

doi:10.1117/12.198608

4 January 1995 Finding shortest paths on surfaces by fast global approximation and precise local refinement

Ron Kimmel, Nahum Kiryati

Proceedings Volume 2356, Vision Geometry III; (1995) https://doi.org/10.1117/12.198608
Event: Photonics for Industrial Applications, 1994, Boston, MA, United States

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.

Citation Download Citation

Ron Kimmel and Nahum Kiryati "Finding shortest paths on surfaces by fast global approximation and precise local refinement", Proc. SPIE 2356, Vision Geometry III, (4 January 1995); https://doi.org/10.1117/12.198608

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available