Approximating minimum-cost polygonal paths of bounded number of links in weighted subdivisions
Ovidiu Daescu, Joseph S. B. Mitchell, Simeon C. Ntafos, James Dean Palmer, Chee Keng Yap · 2006
This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+e) times the length of a shortest k-link path, for any fixed e>0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+e)-approximation algorithms, which guarantee at most 5k−2 links.