Rubberband algorithms for solving various 2D or 3D shortest path problems
Fajie Li and Reinhard Klette
Auckland University, New Zealand


This talk provides a complete discussion of an algorithm (called rubberband algorithm}, which was proposed by Buelow and Klette in 2000 in an IEEE PAMI paper for the calculation of minimum-length polygonal curves in cube- curves in 3D space. In the talk, this original algorithm is transformed ``step-by-step'' into a general, provably correct, and time-efficient algorithm which solves the indented task for simple cube-curves of any complexity (based on results of a recent PhD project by Fajie Li). Variations of this algorithm are then used to solve different Euclidean shortest path (ESP) problems, such as calculating the ESP inside of a simple cube arc, inside of a simple polygon, on the surface of a convex polytope, or inside of a simply-connected polyhedron. -- The developed general (!) methodology of rubberband algorithms was applied in the PhD project by Fajie Li to improve various results of best algorithms for the touring polygons, parts cutting, safari and zookeper, and the watchman route problem.

back to the list of talks