A chromatic art gallery problem

Abstract

The art gallery problem asks for the smallest number of guards required to see every point of the interior of a polygon $P$. We introduce and study a similar problem called the chromatic art gallery problem. Suppose that two members of a finite point guard set $S \\subset P$ must be given different colors if their visible regions overlap. What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon $P$? We call this number, $\\chi_G(P)$, the chromatic guard number of $P$. We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas. We show that for any spiral polygon $P_{spi}$, $\\chi_G(P_{spi}) \\leq 2$, and for any staircase polygon (strictly monotone orthogonal polygon) $P_{sta}$, $\\chi_G(P_{sta}) \\leq \\sqrt{72n} + 15$. We also show that for any positive integer $k$, there exists a polygon $P_k$ with $3k^2 + 2$ vertices such that $\\chi_G(P_k) \\geq k$.