TY - UNPB
T1 - Sometimes Two Irrational Guards are Needed
AU - Meijer, Lucas
AU - Miltzow, Till
PY - 2022
Y1 - 2022
N2 - In the art gallery problem, we are given a closed polygon P, with rational coordinates and an integer k. We are asked whether it is possible to find a set (of guards) G of size k such that any point p∈P is seen by a point in G. We say two points p, q see each other if the line segment pq is contained inside P. It was shown by Abrahamsen, Adamaszek, and Miltzow that there is a polygon that can be guarded with three guards, but requires four guards if the guards are required to have rational coordinates. In other words, an optimal solution of size three might need to be irrational. We show that an optimal solution of size two might need to be irrational. Note that it is well-known that any polygon that can be guarded with one guard has an optimal guard placement with rational coordinates. Hence, our work closes the gap on when irrational guards are possible to occur.
AB - In the art gallery problem, we are given a closed polygon P, with rational coordinates and an integer k. We are asked whether it is possible to find a set (of guards) G of size k such that any point p∈P is seen by a point in G. We say two points p, q see each other if the line segment pq is contained inside P. It was shown by Abrahamsen, Adamaszek, and Miltzow that there is a polygon that can be guarded with three guards, but requires four guards if the guards are required to have rational coordinates. In other words, an optimal solution of size three might need to be irrational. We show that an optimal solution of size two might need to be irrational. Note that it is well-known that any polygon that can be guarded with one guard has an optimal guard placement with rational coordinates. Hence, our work closes the gap on when irrational guards are possible to occur.
U2 - 10.48550/arXiv.2212.01211
DO - 10.48550/arXiv.2212.01211
M3 - Preprint
SP - 1
EP - 19
BT - Sometimes Two Irrational Guards are Needed
PB - arXiv
ER -