Exact and approximate algorithms for the calculation of shortest paths

Abstract

This report 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 report 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 Euclidean shortest path (ESP) problems, such as calculating the ESP inside a simple cube arc, inside a simple polygon, on the surface of a convex polytope, or inside a simply connected polyhedron.Finally, the developed methodology of rubberband algorithms is applied to improve various results of best algorithms for the touring polygons, parts cutting, safari and zookeper, and the watchman route problem.v 1.5.Structure of Report 13Chapter 11 applies the basic idea of the original rubberband algorithm to solve some classic problems such as safari (restricted solution only), zookeeper (restricted solution only) and watchman route problems.Chapters 12 concludes the report.O m 3 n 3 loglog(mn) log(mn)Chapter 3 MLPs of Decomposable Simple Cube CurvesThis chapter develops a provably correct MLP algorithm for a special type of first-class simple cube-curves which can be decomposed (in a particular way) into a finite number of simple cube-arcs.[The next chapter will also show that the formulas derived for these simple cubearcs are important for a correctness proof for the original rubberband algorithm, considering the same special type of cube-curves.]Chapter 4 MLPs of First-Class Simple Cube CurvesThis chapter provides two correctness proofs for the original rubberband algorithm assuming that the input is restricted to first-class simple cube-curves only.The first proof is longer, but also allows to prove the uniqueness of the MLP.The second proof is rater short, and not containing such a uniqueness proof.[The developed proof methodology is later (in Chapter 6) generalized to prove theorems about general simple cube-curves.]Chapter 5 Analysis of the Original AlgorithmThis chapter proves that the original rubberband algorithm has -linear time complexity () O(m), where () is as in Equation (1.1), and m is the number of critical edges of a given simple cube curve.This answers a question for this algorithm, which had been open so far.However, we also find two counterexamples to Option 2 of the original rubberband algorithm (for non-first-class simple cube-curves) which lead to a correction of Option 3 (by adding one missing test) of the original rubberband algorithm.These counterexamples were found by studying the following open problem, as formulated in [85]: Is there a simple cube-curve such that none of the nodes of its MLP is a grid vertex?This chapter constructs an example of such a simple cube-curve, and we also characterize the class of all of such cube-curves. Chapter 6 MLPs of Simple Cube-CurvesThis chapter finally answers a main open problem.By a further modification of the corrected (i.e., in its Option 3) rubberband algorithm we obtain a provably correct and provably lineartime algorithm for calculating the MLP of any simple cube-curve.The chapter also presents an alternative (provably correct and provably linear-time) algorithm for the same task, which is based on moving vertices within faces of cubes rather than moving vertices along critical edges. Chapter 8 ESPs in Simple PolygonsLet p and q be two points in a simple polygon .An open problem in computational geometry asks to devise a simple linear-time algorithm for computing a shortest path between p and q, which is contained in , such that the algorithm does not depend on a (complicated) linear-time triangulation algorithm.This chapter provides an algorithm towards a solution of this problem by applying the rubberband algorithm.The obtained solution has () O(n log n) time complexity (where the super-linear time complexity is only due to preproc