On approximations to minimum link visibility paths in simple polygons

2020/07/14 by Zarrabi, Mohammad Reza, Charkari, Nasrollah Moghaddam
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2007.07329

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(kn²) runtime that produces polygonal visibility paths (or tours) of link-length at most (γ+a_l/(k-1))Opt (or (γ+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³) time approximation algorithm for the graphic traveling salesman problem (path or tour version).

Related

• Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons
• Space-efficient Algorithms for Visibility Problems in Simple Polygon
• Approximation Algorithms for the Two-Watchman Route in a Simple Polygon
• k-Transmitter Watchman Routes
• A sufficient condition for visibility paths in simple polygons