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