Files:
[PDF] 375.5kB [gzipped postscript] 458.0kB
Abstract:
We study a variant of the classical art gallery problem, where an art gallery is modeled by a polygon with curvilinear sides. We focus on \pconvex and \pconcave polygons, which are polygons whose sides are convex and concave arcs, respectively. It is shown that for monitoring a \pconvex polygon with $n\geq 2$ vertices, $łfloor\frac2n3\rfloor$ vertex guards are always sufficient and sometimes necessary. We also present an algorithm for computing at most $łfloor\frac2n3\rfloor$ vertex guards in $O(nłog n)$ time and $O(n)$ space. For the number of point guards, can be be stationed at any point in the polygon, our upper bound $łfloor\frac2n3\rfloor$ carries over and we prove a lower bound of $łceil \fracn2\rceil$. For monitoring a \pconcave polygon with $n\geq 3$ vertices, $2n-4$ point guards are always sufficient and sometimes necessary, whereas there are \pconcave polygons where some points in the interior are hidden from all vertices, hence they cannot be monitored by vertex guards. We conclude with bounds for some special types of curvilinear polygons.
BibTeX:
@Article{kt-artgal-2008, author = {Menelaos I. Karavelas and Csaba D. T\'oth and Elias P. Tsigaridas}, title = {Guarding curvilinear art galleries with vertex or point guards}, journal = CGTA, month = {Aug}, volume = 42, number = {6-7}, pages = "522-535", year = 2009, abstract = " We study a variant of the classical art gallery problem, where an art gallery is modeled by a polygon with curvilinear sides. We focus on \pconvex and \pconcave polygons, which are polygons whose sides are convex and concave arcs, respectively. It is shown that for monitoring a \pconvex polygon with $n\geq 2$ vertices, $\lfloor\frac{2n}{3}\rfloor$ vertex guards are always sufficient and sometimes necessary. We also present an algorithm for computing at most $\lfloor\frac{2n}{3}\rfloor$ vertex guards in $O(n\log n)$ time and $O(n)$ space. For the number of point guards, can be be stationed at any point in the polygon, our upper bound $\lfloor\frac{2n}{3}\rfloor$ carries over and we prove a lower bound of $\lceil \frac{n}{2}\rceil$. For monitoring a \pconcave polygon with $n\geq 3$ vertices, $2n-4$ point guards are always sufficient and sometimes necessary, whereas there are \pconcave polygons where some points in the interior are hidden from all vertices, hence they cannot be monitored by vertex guards. We conclude with bounds for some special types of curvilinear polygons.", }
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02