Minimum-link paths among obstacles in the plane (Q1201747)

Link distance between two points in the plane is defined as the minimum number of edges needed for their interconnection avoiding intersection with prescribing simple-polygonal obstacles. The motivation comes from robot motion planning where the aim is to minimize the number of path bends. The authors developed an algorithm of \(O(E \alpha(n) \log^ 2n)\) time complexity, where \(E\) is the size of corresponding visibility graph, and \(\alpha(n)\) is the inverse of Ackermann's function. The lower bound of order \(\Omega(n \log n)\) is established. Related results are also discussed.