## February 24, 2017:

#
Irrational Guards are Sometimes Needed

##
Grady Yu

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 such 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 fully 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
polygon which can be guarded by $3n$ guards with irrational coordinates
but need $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.

(Based on a preprint
by Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow.)