Hiding people in polygons (Q1122366): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q701798 |
||
Property / reviewed by | |||
Property / reviewed by: Hans-Dietrich Hecker / rank | |||
Revision as of 10:15, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hiding people in polygons |
scientific article |
Statements
Hiding people in polygons (English)
0 references
1989
0 references
Given a polygon P, a hidden (vertex-) set is a set of points (vertices) such that no two points in the set are visible to each other. A (vertex-) guard set is a set of points (vertices) such that each point of P is visible to some point in the guard set. With the help of the NP- completeness of the problem 3-SAT the author shows that the problem of finding a maximum hidden set is NP-hard. A hidden guard set is a hidden set which is also a guard set. The problem of finding a minimum hidden guard set is shown to be NP-complete. For hidden vertex sets and hidden vertex guard sets similar results are obtained.
0 references
visibility
0 references
guarding
0 references
m-convexity
0 references
polygon
0 references
NP-complete
0 references