loading...
Rubberband Algorithms for Solving Various 2D or 3D Shortest Path Problems
Kolkata, India March 05-March 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICCTA.2007.113International Conference on Computing ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fajie Li, The University of Auckland, New Zealand
Reinhard Klette, The University of Auckland, New Zealand
This reviewing paper provides a complete discussion of an algorithm (called rubberband algorithm), which was proposed by B?ulow and Klette in 2000 - 2002 for the calculation of minimum-length polygonal curves in cube-curves in 3D space. The paper describes how this original algorithm was transformed afterwards, "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 various 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, demonstrating a general (!) methodology of rubberband algorithms. The paper also reports how such algorithms improve various time complexity results of best algorithms for problems such as the touring polygons, parts cutting, safari and zookeeper, and the watchman route.
Citation:
Fajie Li, Reinhard Klette, "Rubberband Algorithms for Solving Various 2D or 3D Shortest Path Problems," iccta, pp.9-19, International Conference on Computing: Theory and Applications (ICCTA'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.