On approximations to minimum link visibility paths in simple polygons

We investigate a practical variant of the well-known polygonal visibility path (watchman) problem. For a polygon P, a minimum link visibility path is a polygonal visibility path in P that has the minimum number of links. The problem of finding a minimum link visibility path is NP-hard for simple polygons. If the link-length (number of links) of a minimum link visibility path (tour) is Opt for a simple polygon P with n vertices, we provide an algorithm with O (kn(2)) runtime that produces polygonal visibility paths (or tours) of link-length at most (gamma + a(l)/( k - 1 )) Opt (or (gamma + a(l)/k ) Opt), where k is a parameter dependent on P, a(l) is an output sensitive parameter and gamma is the approximation factor of an O(k(3)) time approximation algorithm for the geometric travelling salesman problem (path or tour version).