Abstract:
Let p and q be two points in a simple polygon P. This chapter provides two rubberband algorithms for computing a shortest path between p and q that is contained in P. The two algorithms are based on previously known results on triangular or trapezoidal decompositions of simple polygons, and have either kappa(epsilon) times O(n) or kappa(epsilon) times O(n log n) time complexity, where kappa(epsilon) = (L0 - L)/epsilon, for the true length L of the shortest path and length L0 of a used initial polygonal path. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithms ar easy to implement (after having the decompositions at hand).
Description:
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s).