protéger la galerie d’Apollon au Louvre ?

L’algorithme pour placer les caméras

Première étape :
On divise la galerie en triangles dont les sommets sont des sommets du polygone. (C’est toujours possible.)

Nous voyons, à la figure 10, une manière de le faire pour notre première galerie.

Figure 10

Deuxième étape :
On colorie les sommets du polygone de trois couleurs, de telle sorte que les sommets de chaque triangle soient de couleurs différentes. (C’est toujours possible.)

Voici, à la figure 11, une manière de le faire.

Figure 11

Cette galerie a 13 sommets : quatre sont verts, quatre sont rouges, et cinq sont bleus. 

On place les caméras aux sommets de la couleur apparaissant le moins souvent. Ici, on a le choix entre le rouge ou le vert. L’algorithme nous donne une solution avec quatre caméras. Supposons que les caméras soient placées aux sommets rouges. Chaque triangle a exactement un sommet rouge. Donc, il est surveillé par la caméra placée en ce sommet. Ceci est vrai pour tous les triangles. On en conclut que les caméras rouges surveillent toute la galerie.  

La solution n’est pas unique. La figure 12 présente une autre manière de découper la galerie en triangles et de colorier les sommets:

Figure 12

Ici, on a deux sommets verts, six sommets rouges et cinq sommets bleus. On place les caméras aux sommets verts et l’algorithme nous donne une solution à deux caméras, plus économique que la précédente.

L’algorithme peut-il toujours nous donner la solution optimale ? Non, on a eu de la chance avec la galerie précédente. Mais, on voit qu’on a avantage à choisir une division utilisant beaucoup de triangles partageant un même sommet. 

Revenons à la galerie d’Apollon

C’est une grande galerie rectangulaire avec des fenêtres sur une longueur. Les murs sont épais si bien que les fenêtres sont enfoncées. On veut surveiller toutes les encoignures des fenêtres. Sinon, une unique caméra suffirait à surveiller la galerie. On représente schématiquement la forme de la galerie incluant les encoignures de fenêtres par le polygone de la figure 13.

Figure 13

(Remarquons qu’on aurait pu allonger la galerie et ajouter des fenêtres.) Voici, à la figure 14, un découpage en triangles et un coloriage associé des sommets.

Figure 14

On a trois fenêtres, quatre sommets rouges, cinq sommets verts et sept sommets bleus. On place donc les caméras aux sommets rouges. L’algorithme, qu’on aurait pu généraliser à plus de fenêtres, nous donne qu’on a besoin d’une caméra de plus que le nombre de fenêtres. En fait, la caméra rouge au coin inférieur droit est inutile. 

Il suffit de placer une caméra à chaque fenêtre pour surveiller toute la galerie, y compris les encoignures de fenêtres. Par contre, vous pouvez vous convaincre qu’il est impossible de surveiller toute la galerie sans avoir au moins une caméra à un des quatre sommets associés à chaque fenêtre. 

Et pour finir, voici deux galeries sur lesquelles vous pouvez vous amuser à faire marcher l’algorithme.

Figure 15

Figure 16

Une meilleure borne pour les polygones orthogonaux

Un résultat affirme qu’on peut diviser l’intérieur d’un polygone orthogonal en quadrilatères convexes et colorer les sommets du polygone avec quatre couleurs de telle sorte que les sommets de chaque quadrilatère soient de couleurs distinctes. 

Comme précédemment, on place les caméras aux sommets de la couleur qui apparait le moins souvent. Cet algorithme donne une meilleure borne pour le nombre maximal de caméras, soit [
n4], dans le cas des polygones orthogonaux. Mais, diviser le polygone en quadrilatères convexes n’est pas toujours facile. On peut commencer la décomposition et se heurter à l’impossibilité de continuer. Il faut alors recommencer. 

À la figure 17, voici une décomposition en quadrilatères convexes pour la galerie de la figure 16.

Figure 17

On a 11 sommets rouges, 11 sommets jaunes, 12 sommets verts, 12 sommets bleus. Donc, ceci donne une solution à 11 caméras en les plaçant, soit aux sommets rouges, ou encore aux sommets jaunes. Aucune de ces deux solutions n’est optimale. En effet, la figure 18 montre qu’on peut surveiller la galerie avec sept caméras.

Figure 18

À la figure 19, on voit une solution optimale à trois caméras aux sommets rouges pour la galerie d’Apollon. (Remarque : plusieurs quadrilatères convexes ont l’air de triangles parce qu’ils ont deux côtés alignés. Ceci vient du fait que le polygone initial a quatre côtés sur une même ligne.)

Figure 19

Bref historique et contexte scientifique

Le problème de la galerie d’art a été proposé en 1973 par le mathématicien Victor Klee au mathématicien Václav Chvátal. Ce dernier l’a résolu en 1975. La preuve algorithmique présentée précédemment est celle de Steve Fisk en 1978. Elle utilise des méthodes très importantes dans des problèmes modernes en mathématiques appliquées, soit la décomposition d’un polygone en triangles, appelée triangulation, et le coloriage de graphes : en effet, les sommets du polygone et les arêtes des triangles forment un graphe. 

En pratique, même si la méthode est connue, elle n’est pas nécessairement facile à programmer. L’ordinateur ne raisonne pas avec une représentation graphique. La donnée d’un polygone est celle d’une énumération des sommets lorsqu’on parcourt la frontière. Le défi est alors d’écrire un programme qui propose un positionnement de caméras, sans que le temps d’exécution du programme n’explose quand le nombre de sommets est grand.