APX-Hardness of the Minimum Vision Points Problem

07/10/2022
by   Mayank Chaturvedi, et al.
0

Placing a minimum number of guards on a given watchman route in a polygonal domain is called the minimum vision points problem. We prove that finding the minimum number of vision points on a shortest watchman route in a simple polygon is APX-Hard. We then extend the proof to the class of rectilinear polygons having at most three dent orientations.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset