Studying Lower Bounds for Conflict-free Colouring of Guards in Polygons

Art gallery problem is to determine the number of guards that are sufficient to see or cover all points in $P$. Consider the problem of placing colour guards in an $n$-sided polygon $P$ such that every point $z \in P$ sees one guard whose colour is different from all other guards visible from $z$. Such placement of colour guards is known as weak conflict-free colouring of $P$.

We derive a lower bound of $\Omega(\log \log n)$ for weak conflict-free colouring of point guards in a simple polygon. There is no non-trivial lower bound known for point guards. For the same problem in a polygon $F$ with holes, we also derive a lower bound of $\Omega(\log n)$, where the guards are allowed to be placed at all locations inside $F$ except some designated locations.