Tata Institute of Fundamental Research

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

Master's Thesis Seminar
Speaker: Suneel Sarswat
Date: Thursday, 19 Feb 2015, 16:00 to 17:00
Venue: AG-80

(Scan to add to calendar)
Abstract:  Abstract: 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.