Problema de Steiner

Supóngase que se quiere localizar una fábrica que trabaja con materiales procedentes de seis almacenes, minimizando la suma resultante de las distancias de transporte. La ubicación que cumple este criterio es la mediana geométrica y con respecto a los seis almacenes x_i. La mediana geométrica de un conjunto discreto de puntos de una muestra en un espacio euclídeo es el punto que minimiza la suma de las distancias a los puntos de la muestra. 

El punto de Fermat o de Torricelli da una solución a la mediana geométrica y al problema del árbol de Steiner para tres puntos. Su nombre se debe a que el problema fue planteado originalmente por Fermat en una carta privada a Evangelista Torriceli, quien lo resolvió. Su pupilo, Viviani, publicó la solución en 1659. La solución a este problema, dada por Torriceli, es la siguiente: Siempre que los ángulos de un triángulo sean inferiores a 120º, el punto cuya distancia total a los vértices del triángulo es mínima se obtiene con la intersección de los tres arcos capaces de 120º de cada lado, esto es, cada arco capaz “ve” a su correspondiente lado del triángulo bajo un ángulo de 120º. El punto de Fermat da una solución a la mediana geométrica y al problema del árbol de Steiner para tres puntos.

Dados n puntos en el plano, encontrar la red que los conecta que tenga longitud mínima. Este problema de optimización combinatoria, nombrado en honor de Jakob Steiner, consiste en buscar la interconexión más corta para un conjunto dado de puntos del plano euclídeo (se usa la distancia euclídea). Este problema tiene multitud de aplicaciones que están relacionadas con el ahorro de material y con el transporte: logística y distribución, ubicación de sedes y sucursales, ubicación de fábricas y almacenes, conexión de una instalación, conexión de una red LAN de ordenadores, cableado, fabricación de chips y circuitos eléctricos, telecomunicaciones... Ha sido demostrado que la conexión resultante es un grafo tipo árbol, llamado árbol de Steiner. Pueden existir varios árboles de Steiner para un conjunto dado de vértices iniciales. La mayoría de las versiones del problema de Steiner son NP-completos. Algunos casos restringidos pueden ser resueltos por tiempo polinómico; sin embargo, en la práctica se usa la heurística.