Problème de la galerie d'art

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ée par un polygone simple et chaque gardien par un point du polygone. Un ensemble $S$ de points est dit surveiller ou couvrir un polygone si, pour tout point $p$ du polygone, il existe un point $q\in S$ tel que le segment de droite entre $p$ et $q$ 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

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 à $n$ sommets, $\lfloor n/3\rfloor$ gardiens suffisent, et cette borne peut être atteinte ».

Historique

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 algorithmiqueModèle:,Modèle:,Modèle:,Modèle:,Modèle:,Modèle:,.

La démonstration de Fisk

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 en haut à gauche, et au nœud vert en bas.

La preuve de Steve FiskModèle:Sfn est courte et élégante : elle figure dans le livre Raisonnements divins. La preuve est pour l'essentiel comme suit. On commence par trianguler le polygone (sans ajouter de nouveaux sommets). On procède comme pour la triangulation : On utilise le fait que tout polygone simple à au moins quatre sommets possède au moins deux « oreilles ». Une oreille est un triangle avec deux arêtes appartenant à la frontière du polygone, et la troisième située à l'intérieur du polygone. L'algorithme consiste à trouver une telle oreille, à la retirer du polygone, ce qui donne un nouveau polygone plus petit, donc 3-coloriable par récurrence, et ce coloriage est facilement étendu en coloriant le sommet supplémentaire de l'oreille avec la couleur restante. Dans une coloration en 3 couleurs, chaque triangle doit comporter les 3 couleurs. Les sommets de l'une des couleurs forment un ensemble de gardiens valide puisque chaque triangle du polygone est gardé par son sommet de cette couleur. Comme les trois couleurs partitionnent les n sommets du polygone, la couleur avec le moins de sommets définit un ensemble de gardiens valides avec au plus $\lfloor n/3\rfloor$ gardiens.

Illustration de la preuve

Pour illustrer la preuve, on considère le polygone ci-dessous. La première étape consiste à trianguler le polygone (voir Figure 1). Ensuite, on applique un

$3$

-coloriage correct (Figure 2) et on observe qu'il y a

$4$

sommets rouges,

$4$

bleus et

$6$

verts. La couleur ayant le moins de sommets est le bleu ou le rouge, donc le polygone peut être couvert par

$4$

gardes (Figure 3). Ceci est en accord avec le théorème de la galerie d'art, car le polygone a

$14$

sommets, et

$\lfloor \frac{14}{3}\rfloor =4$

.

• 
  Figure 1
• 
  Figure 2
• 
  Figure 3

Variantes

Problème de la forteresse. Pour 13 sommets, il faut 5 gardiens.

La majoration de Chvátal reste valable si la restriction des gardiens aux sommets est affaiblie à des gardiens à tout point qui n'est pas à l'extérieur du polygone.

Il existe d'autres généralisations ou spécialisations du théorème de la galerie d'art original. Par exemple, pour les polygones orthogonaux, c'est-à-dire des polygones dont les côtés se joignent à angle droit, il suffit de $\lfloor n/4\rfloor$ gardiens. Il existe au moins trois démonstrations différentes de ce résultat, aucune n'est simple, l'une par Kahn, Maria Klawe et Daniel Kleitman; une autre par Anna Lubiw; et encore une autre par Jörg-Rüdiger Sack et Modèle:Lien.

Un problème similaire consiste à déterminer le nombre minimal de gardiens nécessaires pour couvrir l'extérieur d'un polygone (c'est le « problème de la forteresse »): $\lceil n/2\rceil$ sont suffisants et parfois aussi nécessaires. En d'autre termes, couvrir l'extérieur, qui est infini, est plus exigeant que de couvrir l'intérieur fini.

Complexité algorithmique

Le problème de calcul

Des algorithmes efficaces existent pour trouver des ensembles de gardiens placés aux sommets du polygone et qui vérifient la majoration de Chvátal, donc d'au plus $\lfloor n/3\rfloor$ gardiens.

David Avis et Godfried Toussaint ont prouvé qu'un tel placement peut être calculé en temps $O(n\log n)$ dans le pire des cas, en utilisant une méthode de diviser pour régner. Modèle:Harvsp ont donné un algorithme en temps linéaire en utilisant l'algorithme de la preuve de Fisk et l'algorithme linéaire de triangulation de Bernard Chazelle.

Un algorithme de calcul a été proposé par Modèle:Harvsp pour les gardiens placés aux sommets. Les auteurs ont mené de nombreux tests avec diverses classes de polygones qui ont montré que des solutions optimales peuvent être trouvées en un temps relativement court même pour des polygones à plusieurs milliers de sommetsModèle:Note.

Le problème de décision

Considéré comme un problème de décision, le problème de la galerie d'art est le problème de déterminer, étant donné un polygone et un entier k, si ce polygone peut être gardé avec au plus k gardiens. Ce problème est $\mathrm{\exists }ℝ$-complet, où $\mathrm{\exists }ℝ$ est la classe de complexité qui correspond au fragment existentiel de la théorie des corps réels clos. Les variations usuelles (comme restreindre les positions des gardiens aux sommets ou aux arêtes du polygone) sont NP-difficiles.

Approximation

En ce qui concerne un algorithme d'approximation pour le nombre minimum de gardiens, Modèle:Harvsp ont montré que le problème est APX-difficile ; ceci implique qu'il est peu probable qu'un rapport d'approximation meilleur qu'une constante fixée puisse être réalisé par un algorithme d'approximation en temps polynomial. Toutefois, on ne connaît pas d'algorithme avec un rapport d'approximation constant. En revanche, une approximation logarithmique du nombre minimum de gardien peut être obtenue en réduisant le problème au problème de couverture par ensembles. Il a été montré par Pavel Valtr que le système d'ensembles dérivé d'un problème de galerie d'art a une dimension de Vapnik-Tchervonenkis bornée, ce qui permet d'appliquer des algorithmes de couverture par ensembles basés sur des Modèle:Lien dont le rapport d'approximation est le logarithme du nombre optimal de gardiens plutôt que du nombre de sommets du polygone. Pour le cas de gardiens sans restriction sur leur position, le nombre potentiellement infini des positions rend le problème encore plus difficile. Si l'on force les gardiens à occuper des positions sur une grille fine, un algorithme d'approximation logarithmique plus compliqué peut être obtenu sous des hypothèses additionnelles peu contraignantes.

Dimensions supérieures

Exemple d'un polyèdre avec des points à l'intérieur qui ne sont visibles d'aucun de ses sommets.

Si le musée est représenté en dimension supérieure par un polyèdre, alors il peut ne pas suffire de positionner un gardien sur chaque sommet pour couvrir la totalité du musée. Même si les surfaces du polyèdre sont alors sous surveillance, il est possible que des points à l'intérieur du polyèdre ne puissent pas être visibles.

Références

Livres

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.

Articles

• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.

• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.

Voir aussi

Articles connexes

• Modèle:Lien
• Graphe planaire extérieur
• Nombre de Catalan
• Modèle:Lien
• Triangulation de Delaunay
• Triangulation d'un ensemble de points
• Triangulation d'un polygone
• Géométrie algorithmique
• Problème de l'éclairage