Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm

摘要: Let p and q be two points in a simple polygon Π. An open problem computational geometry asks to devise linear-time algorithm for computing shortest path between q, which is contained Π, such that the does not depend on (complicated) triangulation algorithm. This report provides contribution solution of this by applying rubberband The obtained has ${\cal O}$ (nlogn) time complexity (where super-linear only due preprocessing, i.e. calculation critical edges) is, altogether, considerably simpler than It applications 2D pattern recognition, picture analysis, robotics, so forth.