Computing a shortest k-link path in a polygon

The authors consider the problem of finding a shortest polygonal path from s to t within a simple polygon P, subject to the restriction that the path have at most k links (edges). They give an algorithm to compute a k-link path with length at most (1 + ε) times the length of a shortest k-link path, for any error tolerance ε>0. The algorithm runs in time O(n³k³ log (Hk/ε¹k/)), where N is the largest integer coordinate among the n vertices of P. They also study the more general problem of approximating shortest k-link paths in polygons with holes. In this case, they give an algorithm that returns a path with at most 2k links and length at most that of a shortest k-link path; the running time is O(kE²), where E is the number of edges in the visibility graph. Finally, they study the bicriteria path problem in which the two criteria are link length and `total turn´ (the integral of |Δθ| along a path). They obtain in an exact polynomial-time algorithm for polygons with holes