Arbres de Steiner

 

Minimiser la longueur des réseaux qui connectent un ensemble de points est l'un des plus vieux problèmes d'optimisation mathématique. Au milieu du  XIIième siècle est apparu le problème élémentaire suivant : minimiser la somme des distances d'un point P aux sommets d'un triangle (ABC). Cette question fut résolue indépendamment par Fermat, Torricelli et Cavalieri qui établirent qu'un tel minimum est atteint soit par un sommet, soit par un point interne au triangle pour lequel les demi-droites (PA), (PB), (PC) forment des angles de 120 degrés. Au XIXième siècle, Jakob Steiner généralisa ce problème à un ensemble de m points; à m points fixés, appelés sommets, on cherche à associer un réseau connexe de longueur minimale qui les contient. On montre facilement qu'un tel réseau est constitué uniquement de segments. D'autres points que les m sommets peuvent apparaître dans un réseau optimal; ils sont appelés points de Steiner. Nous retiendrons quatre aspects géométriques d'une structure optimale :

En 1977, la NP-complétude du problème de Steiner est établie. Depuis, un grand nombre d'algorithmes ont été développés permettant d'apporter des solutions exactes ou approchées au problème de Steiner. Notre but ici n'est en aucun cas de concurrencer de tels travaux ; nous nous contentons d'illustrer comment une approche stochastique non structurée peut permettre de décrire numériquement une configuration de Steiner optimale. Nous  présentons quelques résultats obtenus pour des ensembles de points (rouges) donnés du plan ou de l'espace.


Configuration approchée (à gauche) et configuration exacte (à droite).

Configuration approchée (à gauche) et configuration exacte (à droite).


Configuration approchée (à gauche) et configuration exacte (à droite).

Arbre de Steiner associé aux sommets d'un cube. Arbre de Steiner associé à une configuration en étoile.

 

Autres sites consacrés au problème de Steiner :