The complexity of guarding monotone polygons

E Krohn, BJ Nilsson - Canadian Conference on Computational …, 2012 - diva-portal.org
Canadian Conference on Computational Geometry, Charlottetown, Prince …, 2012diva-portal.org
A polygon P is x-monotone if any line orthogonal to the x-axis has a simply connected
intersection with P. A set G of points inside P or on the boundary of P is said to guard the
polygon if every point inside P or on the boundary of P is seen by a point in G. An interior
guard can lie anywhere inside or on the boundary of the polygon. Using a reduction from
Monotone 3SAT, we prove that the decision version of this problem is NP-hard. Because
interior guards can be placed anywhere inside the polygon, a clever gadget is introduced …
Abstract
A polygon P is x-monotone if any line orthogonal to the x-axis has a simply connected intersection with P. A set G of points inside P or on the boundary of P is said to guard the polygon if every point inside P or on the boundary of P is seen by a point in G. An interior guard can lie anywhere inside or on the boundary of the polygon. Using a reduction from Monotone 3SAT, we prove that the decision version of this problem is NP-hard. Because interior guards can be placed anywhere inside the polygon, a clever gadget is introduced that forces interior guards to be placed at very specific locations.
diva-portal.org
以上显示的是最相近的搜索结果。 查看全部搜索结果