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

Abstract:

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