Guarding Art Galleries: The Extra Cost for Sculptures is Linear

Louigi Addario-Berry 1 Omid Amini 2 Jean-Sébastien Sereni 3 Stéphan Thomassé 4
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Art gallery problems have been extensively studied over the last decade and have found different type of applications. Normally the number of sides of a polygon or the general shape of the polygon is used as a measure of the complexity of the problem. In this paper we explore another measure of complexity, namely, the number of guards required to guard the boundary, or the walls, of the gallery. We prove that if n guards are necessary to guard the walls of an art gallery, then an additional team of at most 4n − 6 will guard the whole gallery. This result improves a previously known quadratic bound, and is a step towards a possibly optimal value of n − 2 additional guards. The proof is algorithmic, uses ideas from graph theory, and is mainly based on the definition of a new reduction operator which recursively eliminates the simple parts of the polygon. We also prove that every gallery with c convex vertices can be guarded by at most 2c − 4 guards, which is optimal.
Type de document :
Communication dans un congrès
SWAT'08: 11th Scandinavian Workshop on Algorithm Theory, Jul 2008, Gothenburg, Sweden. Springer, pp.41-52, 2008, LNCS. 〈http://www.dmist.net/swat2008/〉. 〈10.1007/978-3-540-69903-3〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00325147
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:18:13
Dernière modification le : mardi 21 novembre 2017 - 01:23:44
Document(s) archivé(s) le : mardi 4 janvier 2011 - 11:21:11

Fichier

artgallery.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Louigi Addario-Berry, Omid Amini, Jean-Sébastien Sereni, Stéphan Thomassé. Guarding Art Galleries: The Extra Cost for Sculptures is Linear. SWAT'08: 11th Scandinavian Workshop on Algorithm Theory, Jul 2008, Gothenburg, Sweden. Springer, pp.41-52, 2008, LNCS. 〈http://www.dmist.net/swat2008/〉. 〈10.1007/978-3-540-69903-3〉. 〈lirmm-00325147〉

Partager

Métriques

Consultations de la notice

427

Téléchargements de fichiers

234