Guarding curvilinear art galleries with vertex or point guards

Menelaos Karavelas 1 Elias Tsigaridas 2
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : One of the earliest and most well known problems in computational geometry is the so-called \emph{art gallery problem}. The goal is to compute the minimum possible number guards placed on the vertices of a simple polygon in such a way that they cover the interior of the polygon. We consider the problem of guarding an art gallery which is modeled as a polygon with curvilinear walls. Our main focus is on polygons the edges of which are convex arcs pointing towards the exterior or interior of the polygon (but not both), named piecewise convex and piecewise concave polygons. We prove that, in the case of piecewise convex polygons, if we only allow vertex guards, $\lfloor\frac{4n}{7}\rfloor-1$ guards are sometimes necessary, and $\lfloor\frac{2n}{3}\rfloor$ guards are always sufficient. Moreover, an $O(n\log{}n)$ time and $O(n)$ space algorithm is described that produces a vertex guarding set of size at most $\lfloor\frac{2n}{3}\rfloor$. When we allow point guards the afore-mentioned lower bound drops down to $\lfloor\frac{n}{2}\rfloor$. In the special case of monotone piecewise convex polygons we can show that $\lfloor\frac{n}{2}\rfloor+1$ vertex or $\lfloor\frac{n}{2}\rfloor$ point guards are always sufficient and sometimes necessary. In the case of piecewise concave polygons, we show that $2n-4$ point guards are always sufficient and sometimes necessary, whereas it might not be possible to guard such polygons by vertex guards. We conclude with bounds for other types of curvilinear polygons and future work.
Type de document :
Rapport
[Research Report] RR-6132, INRIA. 2007
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00132988
Contributeur : Elias Tsigaridas <>
Soumis le : lundi 18 février 2008 - 21:45:32
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 15:11:07

Fichier

RR-6132.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00132988, version 8

Collections

Citation

Menelaos Karavelas, Elias Tsigaridas. Guarding curvilinear art galleries with vertex or point guards. [Research Report] RR-6132, INRIA. 2007. 〈inria-00132988v8〉

Partager

Métriques

Consultations de la notice

328

Téléchargements de fichiers

124