Home | Gallery | CV | Visit | Publications |
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 :
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 :