DANS CETTE Activité

Le problème de la galerie d'art est un problème bien connu en géométrie computationnelle. Il pose la question suivante : quel est le nombre minimum de gardiens nécessaires pour surveiller une galerie d'art avec n murs, de manière à ce que chaque point de l'intérieur de la galerie soit visible par au moins un gardien.

La version que nous proposons adapte ce problème aux sculptures au lieu des gardiens. L'objectif est similaire : minimiser le nombre de sculptures de telle sorte que, de n'importe quel point à l'intérieur du musée, on puisse voir au moins une sculpture.

Afin de satisfaire les visiteurs, la directrice d’un musée souhaite que depuis n’importe quelle position à l’intérieur du musée, on puisse voir au moins une sculpture. Ces dernières étant difficiles à acquérir, elle essaye néanmoins de réduire au maximum le nombre de sculptures nécessaires pour remplir son musée avec ce critère.

Par exemple, dans la salle ci-dessous (vu de haut), deux sculptures (représentées par des étoiles) suffisent.

Placement de sculptures

Pour chacune des salles, aidez la directrice à trouver le nombre minimum de sculptures pour remplir le musée, et placez les.

Des sculptures et des murs

Une des autres salles a besoin d’au moins 5 sculptures pour être remplie. Quel est le nombre minimum de murs que possède cette salle (on suppose que les murs sont droits, et non courbés).

Nombre de sculptures minimum pour N murs

Combien faut il au minimum de sculptures pour remplir n’importe quelle salle constituée de 9 murs ? Et pour les salles de 10 murs ? Et pour N murs ? Trouvez un algorithme qui permet de remplir n’importe quelle salle, sans dépasser ce nombre minimum.