Abstract:
Let p and q be two points in a simple polygon P. 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 P, such that the algorithm does not depend on a (complicated) linear-time triangulation algorithm. This report provides a contribution to the solution of this problem by applying the rubberband algorithm. The obtained solution has O(nlogn) time complexity (where the super-linear time complexity is only due to preprocessing, i.e. for the calculation of critical edges) and is, altogether, considerably simpler than the triangulation algorithm. It has applications in 2D pattern recognition, picture analysis, robotics, and so forth.
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).