Problème de la galerie d'art

La question sur le nombre de gardiens nécessaires a été posée à Chvátal par Victor Klee en 1973[1]. Chvátal l'a prouvé peu de temps après[2]. La démonstration de Chvátal a été simplifiée par Steve Fisk, au moyen d'un argument basé sur une coloration de graphe[3]. Fisk était alors professeur de mathématiques au Bowdoin College[4].

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[5] - [6] - [7] - [8] - [9] - [10] - [11].

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.

La preuve de Steve Fisk[12] est courte et élégante : elle figure dans le livre Raisonnements divins[13]. 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 ${\displaystyle \lfloor n/3\rfloor }$ gardiens.

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 ${\displaystyle 3}$-coloriage correct (Figure 2) et on observe qu'il y a ${\displaystyle 4}$ sommets rouges, ${\displaystyle 4}$ bleus et ${\displaystyle 6}$ verts. La couleur ayant le moins de sommets est le bleu ou le rouge, donc le polygone peut être couvert par ${\displaystyle 4}$ gardes (Figure 3). Ceci est en accord avec le théorème de la galerie d'art, car le polygone a ${\displaystyle 14}$ sommets, et ${\displaystyle \left\lfloor {\frac {14}{3}}\right\rfloor =4}$.

• 
  Figure 1
• 
  Figure 2
• 
  Figure 3

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[14]. Par exemple, pour les polygones orthogonaux, c'est-à-dire des polygones dont les côtés se joignent à angle droit, il suffit de ${\displaystyle \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 Godfried Toussaint (en)[15].

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 »): ${\displaystyle \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[16].

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 ${\displaystyle \lfloor n/3\rfloor }$ gardiens.

David Avis et Godfried Toussaint[17] ont prouvé qu'un tel placement peut être calculé en temps ${\displaystyle O(n\log n)}$ dans le pire des cas, en utilisant une méthode de diviser pour régner. Kooshesh et Moret 1992 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 Couto, de Rezende et de Souza 2011 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 sommets[18].

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 ${\displaystyle \exists \mathbb {R} }$-complet[19], où ${\displaystyle \exists \mathbb {R} }$ 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[20].

En ce qui concerne un algorithme d'approximation pour le nombre minimum de gardiens, Eidenbenz, Stamm et Widmayer 2001 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[21]. Il a été montré par Pavel Valtr[22] 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 ε-réseaux (en) dont le rapport d'approximation est le logarithme du nombre optimal de gardiens plutôt que du nombre de sommets du polygone[23]. Pour le cas de gardiens sans restriction sur leur position, le nombre potentiellement infini des positions rend le problème encore plus difficile[24]. 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[25].