Irrational Guards are Sometimes Needed
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Irrational Guards are Sometimes Needed. / Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann.
33rd International Symposium on Computational Geometry (SoCG 2017). ed. / Boris Aronov; Matthew J. Katz. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. p. 1-15 3 (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 77).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Irrational Guards are Sometimes Needed
AU - Abrahamsen, Mikkel
AU - Adamaszek, Anna
AU - Miltzow, Tillmann
N1 - Conference code: 33
PY - 2017
Y1 - 2017
N2 - In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon so that the guards together can see the whole polygon. We say that a guard at position x sees a point y if the line segment xy is contained in the polygon. Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every n, there is a polygon which can be guarded by 3n guards with irrational coordinates but needs 4n guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.
AB - In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon so that the guards together can see the whole polygon. We say that a guard at position x sees a point y if the line segment xy is contained in the polygon. Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every n, there is a polygon which can be guarded by 3n guards with irrational coordinates but needs 4n guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.
U2 - 10.4230/LIPIcs.SoCG.2017.3
DO - 10.4230/LIPIcs.SoCG.2017.3
M3 - Article in proceedings
SN - 978-3-95977-038-5}
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
SP - 1
EP - 15
BT - 33rd International Symposium on Computational Geometry (SoCG 2017)
A2 - Aronov, Boris
A2 - Katz, Matthew J.
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Y2 - 4 July 2017 through 7 July 2017
ER -
ID: 196765968