Abstract:
This thesis provides a complete discussion of an algorithm (called rubberband algorithm), which was proposed in 2000 for the calculation of minimum-length polygonal curves in cube curves in 3D space. The thesis transforms it "step-by-step into a general, provably correct, and time-efficient algorithm which solves the indented task for simple cube curves of any complexity. Variations of this algorithm are then used to solve different shortest path problems (exact or approximate, in a general or restricted way). Keywords: Euclidean shortest paths, rubberband algorithm, computational geometry, digital geometry, cube curves.