Euclidean Shortest Paths in a Simple Polygon
Fajie Li, Reinhard Klette · Statistical science and interdisciplinary research · 2008
Let p and q be two points in a simple polygon Π. This chapter provides two rubberband algorithms for computing a shortest path between p and q that is contained in Π. The two algorithms use previously known results on triangular or trapezoidal decompositions of simple polygons, and have eitherO (n) orO (n log n) time complexity (where the super-linear time complexity is only due to