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.
| 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.
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.