Fuente:
Yo estaba programación de la visualización de la distancia Euclídea para el Problema del Viajante cuando me encontré con este problema.
Pregunta:
Considere la posibilidad de una región acotada en el plano Euclidiano, en este caso, vamos a considerar la unidad de la plaza de $[0, 1]\times[0, 1]$.
Vamos a poner el $n$ puntos en su interior.
A continuación, encontramos el camino más corto que pasa a través de todas las $n$ puntos.
¿Dónde colocamos el $n$ puntos tales que la longitud de este camino más corto sea el máximo posible?
Ejemplos:
Para $n=2$, tenemos el camino más largo como la diagonal del cuadrado, con una longitud de $\sqrt{2}$:
Para $n=3$, (de crédito a Fritz para detectar este error) tenemos este camino más largo de la parte de la más grande de un triángulo equilátero en la plaza, de la longitud de la $\frac{8}{\sqrt{6}+\sqrt{2}}$:
La colocación de 4 puntos en las esquinas de la plaza que se va a llevar a este camino, que sospecho que es la más larga, con una longitud de $3$:
Algunos trabajos:
La máxima longitud de la ruta es $\omega(\sqrt{n})$.
Construcción: Organizar la $n$ puntos en una cuadrícula regular de la formación. Ya que los puntos están separados por una distancia de $\Theta\left(\frac{1}{\sqrt{n}}\right)$ e hay $n$ puntos, multiplicando les da la cota de $\omega(\sqrt{n})$
La colocación de los puntos en $\left(\frac{i}{\lceil\sqrt{n}\rceil}, \frac{j}{\lceil\sqrt{n}\rceil}\right)$ daría una forma cerrada límite inferior para el límite superior de $\frac{n-1}{\lceil\sqrt{n}\rceil}$.
Recompensa De Edición:
Estoy interesado en la forma cerrada de los límites para el límite superior (tales como el límite inferior de $\frac{n-1}{\lceil\sqrt{n}\rceil}$ como se mencionó anteriormente). Otros delimitada regiones (tales como la unidad de círculo) puede ser también muy interesante, y también serán considerados para la recompensa.
