On approximations to minimum link visibility paths in simple polygons

Abstract

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(k{n}^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 γ is the approximation factor of an $O(k^3)$ time approximation algorithm for the geometric travelling salesman problem (path or tour version).

Keywords:

• Polygonal paths
• Visibility paths
• Minimum link paths
• Simple polygons

Acknowledgements

We sincerely thank Dr Hadi Shakibian and Dr Ali Rajaei for their kind help and valuable comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 The endpoints of cuts in $\mathcal{C}$ must be sorted in counterclockwise order in the greedy algorithm for computing M.

2 The best known value of γ is 1.5 for finding HPP [9, 10] and 1.4 for finding HT (Hamiltonian Tour) [10].