On approximations to minimum link visibility paths in simple polygons. Issue 4 (1st October 2020)

• Record Type: Journal Article
• Authors: Zarrabi, Mohammad Reza; Charkari, Nasrollah Moghaddam
• Is Part Of: International journal of computer mathematics. Volume 5:Issue 4(2020)
• Page Start: 300
• Page End: 307
• Publication Date: 2020-10-01
• Subjects: Polygonal paths -- Visibility paths -- Minimum link paths -- Simple polygons; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1831612
• Languages: English
• ISSNs: 2379-9927

Abstract

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 ( γ + a l / ( k − 1 ) ) O p t (or ( γ + a l / k ) O p t ), 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).