Variations on the art gallery theorem
Iliana Bjorling-Sachs · 1993
In 1973 Victor Klee posed the question: Given an arbitrarily shaped art gallery with n walls, what is the minimum number of guards required to survey the entire gallery? The guards must remain at fixed locations, but may rotate 360 degrees. The answer, due to Chvatal and known as Chvatal's art gallery theorem, is that $\lfloor n/3\rfloor$ guards are sufficient for any gallery and necessary in some galleries. Many variations of the original problem exist. Galleries can be simple polygons or be restricted in shape e.g. rectilinear. Guards can be stationary or mobile and have limited vision or be able to see any distance and in any direction. Stationary guards may be restricted to positions at vertices or be placed arbitrarily within the polygon. Mobile guards may be restrained to the edges of the polygon, in which case they are called edge guards, or be allowed to cut across open spaces. In this thesis, we provide tight upper bounds on the number of guards needed for two distinct models. For art galleries with h obstacles and n walls, $\lfloor(n+h)/3\rfloor$ stationary guards are always sufficient. For monotone or spiral galleries with a total of n walls, $\lceil(n - 2)/5\rceil$ edge guards are always sufficient. If the gallery is rectilinear in addition to being monotone or spiral then the tight bound changes to $\lceil(n - 2)/6\rceil.$ For stationary guards in galleries with obstructions, we provide an $O(n\sp2)$ algorithm to place the guards. For mobile guards, the associated algorithms run in O(n) time.