论文标题
有时需要两个非理性的后卫
Sometimes Two Irrational Guards are Needed
论文作者
论文摘要
在美术馆问题中，我们为我们提供了一个封闭的多边形$ P $，具有理性的坐标和整数$ k $。询问我们是否可以找到一套（警卫）$ g $ $ k $的套装，以便在$ g $中看到p $的任何点$ p \。我们说，如果线段$ pq $包含在$ p $中，则两个点$ p $，$ q $互相见面。亚伯拉罕森，阿达马斯齐克和米尔特佐（Miltzow）表明，有一个多边形可以用三名后卫保护，但如果需要警卫，则需要四名后卫。换句话说，大小的最佳解决方案可能需要是不合理的。我们表明，大小的最佳解决方案可能需要是不合理的。请注意，众所周知，任何可以用一个后卫保护的多边形都具有最佳的后卫位置，并具有理性的坐标。因此，当可能发生非理性警卫时，我们的工作缩小了差距。
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\in 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.
