APX-Hardness of the Minimum Vision Points Problem
2022
Online
report
Placing a minimum number of guards on a given watchman route in a polygonal domain is called the {\em 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.
Comment: 9 pages, 5 figures. A preliminary version was presented at the 38th European Workshop on Computational Geometry EuroCG 2022
Titel: |
APX-Hardness of the Minimum Vision Points Problem
|
---|---|
Autor/in / Beteiligte Person: | Chaturvedi, Mayank ; Nilsson, Bengt J. |
Link: | |
Veröffentlichung: | 2022 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|