Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème de la galerie d'art
Résumé
vignette|Un polygone simple à 43 côtés représentant une galerie d'art, et quatre caméras couvrent cette galerie.
En informatique, plus précisément en géométrie algorithmique, le problème de la galerie d'art est un problème de visibilité bien étudié inspiré d'un problème réel. Il se formule comme suit :
« Quel est le nombre de gardiens (ou caméras) nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? »
Formellement, la galerie d'art est représenté par un polygone simple et chaque gardien par un point du polygone. Un ensemble de points est dit surveiller ou couvrir un polygone si, pour tout point du polygone, il existe un point tel que le segment de droite entre et est entièrement contenu dans le polygone. On peut aussi interpréter les gardiens comme des caméras de surveillance et demander que l'ensemble de la galerie soit visible en balayage.
Le théorème de la galerie d'art, démontré par Václav Chvátal, donne un majorant du nombre minimal de gardiens. Il dit :
« Pour garder un polygone simple à sommets, gardiens suffisent, et cette borne peut être atteinte ».
La question sur le nombre de gardiens nécessaires a été posée à Chvátal par Victor Klee en 1973. Chvátal l'a prouvé peu de temps après. La démonstration de Chvátal a été simplifiée par Steve Fisk, au moyen d'un argument basé sur une coloration de graphe. Fisk était alors professeur de mathématiques au Bowdoin College.
Le problème et le théorème de la galerie d'art est moins connu que les thèmes standard de la géométrie algorithmique comme l'enveloppe convexe, la triangulation d'un polygone ou le calcul du diagramme de Voronoï, mais il figure dans divers manuels et cours de géométrie algorithmique.
vignette|Une 3-coloration des sommets d'un polygone triangulé. Les sommets d'une même couleur donnent un ensemble de gardiens. Les sommets bleus par exemple fournissent un ensemble non-optimal de 3 gardiens. Il est possible de n'avoir que 2 gardiens, en les plaçant au nœud bleu le plus en haut (et le plus à gauche), et au nœud rouge en bas à droite.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.