Construcción de la curva de interpolación más corta a partir de puntos en $\mathbb R^2$ con ecuaciones paramétricas.

Question

Supongamos que nos dan un conjunto de $n$ puntos de $\mathbb R^2$ , $(x_1,y_1),(x_2,y_2)\dots(x_n,y_n)$ .

Queremos construir un camino que conecte todos estos puntos utilizando un par de ecuaciones paramétricas \begin{cases} x = f(t) \\ y = g(t) \\ \end{cases} tal que \begin{cases} f(0) = f(1) = x_1 \\ g(0) = g(1) = y_1 \\ \end{cases} y encontrar un conjunto de puntos $(t_2,t_3\dots t_n),$ para lo cual \begin{cases} f(t_k) = x_k \\ g(t_k) = y_k \\ \end{cases} y la longitud del camino desde $(x_1,y_1)$ a sí mismo a través de todos los demás puntos se minimiza.

Ahora, encontrar un camino es fácil. Dividir la línea unitaria en $n$ partes, tomar el punto de partida de cada parte para ser $t_k$ y construir dos polinomios de interpolación de grado $n$ , $f_p$ y $g_p$ , de tal manera que $f_p(t_k)=x_k$ y $g_p(t_k)=y_k$ y establecer \begin{cases} x = f_p(t) \\ y = g_p(t) \\ \end{cases}

Ejemplo: Sean los puntos originales $(0,0),(1,1),(2,0)$ y seleccionar puntos de tiempo para ser $(1/3,2/3)$ . Ahora la función de interpolación paramétrica es \begin{cases} x = -\frac{27}{2} (-1 + t) t^2 \\ y = \frac{9}{2} (-1 + t) t (-2 + 3 t) \\ \end{cases}

La longitud de este recorrido se obtiene mediante la fórmula $L=\int_0^1 \sqrt{{\frac{dx}{dt}}^2+{\frac{dy}{dt}}^2} dt$ y es aproximadamente $5.422$ .

Sin embargo, si seleccionamos tiempos para ser $(1/4,3/4),$ obtenemos la función \begin{cases} x = -\frac{8}{3} (-1 + t) t (1 + 4 t) \\ y = \frac{8}{3} (-1 + t) t (-3 + 4 t) \\ \end{cases} y la longitud es ahora aproximadamente $5.411$ .

Por lo tanto, la optimización de la longitud del recorrido requiere dos componentes, la selección de los tiempos $t_k$ y también seleccionando las funciones de interpolación originales. Los tiempos pueden optimizarse mediante métodos de diferenciación normales, pero ¿cómo podemos optimizar sobre las funciones de interpolación? El método para resolver este tipo de problemas es el cálculo de variaciones. ¿Puede aplicarse a este tipo de problemas con interpolación y ecuaciones paramétricas?

Se trata de una especie de variante "continua" del problema del viajante de comercio y esperaba poder obtener de ella algunos métodos más rápidos y robustos para resolver el TSP en general, pero al observar los ejemplos más sencillos, me doy cuenta de que tanto las funciones de interpolación como las integraciones necesarias se vuelven excesivamente complejas muy rápidamente. Entonces, ¿hay algún método para simplificar el proceso?

Edición: ¿Existe una forma rápida de conseguir una buena selección de $t_k$ s?

Answer 1

Se quiere construir un polinomio de n grados para n puntos. En su ejemplo tome las funciones como $$x(t)=at^3+bt^2+ct+d$$ $$y(t)=kt^3+lt^2+mt+n$$ La primera condición $x(0)=y(0)=0$ requiere que $d=n=0$ . Su segunda condición $x(1)=y(1)=0$ puede satisfacerse si $c=-(a+b)$ y $m=-(k+l)$ $$\Rightarrow x(t)=at^3+bt^2-(a+b)t$$ $$\Rightarrow y(t)=kt^3+lt^2-(k+l)t$$ Ahora se puede hacer una simplificación para la integral. Podemos minimizar $\int f(t)\,dt$ en lugar de $\int \sqrt{f(t)}\, dt$ . $$I(a,b,k,l)=\int_0^1 \bigg(\big(3at^2+2bt-(a+b)\big)^2+\big(3kt^2+2lt-(k+l)\big)^2\bigg) \, dt$$ $$I(a,b,k,l)=\frac{4 a^2}{5}+a b+\frac{b^2}{3}+\frac{4 k^2}{5}+k l+\frac{l^2}{3}$$ Ahora debes imponer condiciones interiores. Para $x(t)$ se deduce que $$x(t_1)=2\text{ and }x(t_2)=1$$ $$\Rightarrow a=-\frac{-\text{t1}+\text{t1}^2+2 \text{t2}-2 \text{t2}^2}{\text{t1} \left(-\text{t1}+\text{t1}^2+\text{t2}-\text{t1} \text{t2}\right) \left(-\text{t2}+\text{t2}^2\right)}$$ $$\Rightarrow b=-\frac{\text{t1}-\text{t1}^3-2 \text{t2}+2 \text{t2}^3}{(-1+\text{t1}) \text{t1} (\text{t1}-\text{t2}) (-1+\text{t2}) \text{t2}}$$ Para $y(t)$ $$y(t_1)=0\text{ and }y(t_2)=1$$ $$\Rightarrow k=-\frac{1}{(\text{t1}-\text{t2}) \left(-\text{t2}+\text{t2}^2\right)}$$ $$\Rightarrow l=-\frac{-1-\text{t1}}{(\text{t1}-\text{t2}) (-1+\text{t2}) \text{t2}}$$ Ahora podemos sustituir $a,b,k,l$ como funciones de $t_1,t_2$ . Para minimizar la integral utilizamos las primeras derivadas $$\frac{\partial I}{\partial t_1}=\frac{\partial I}{\partial t_2}=0$$ Al resolver el sistema anterior se obtienen los siguientes conjuntos de soluciones $$t_1=0.33\text{ and }t_2=0.74\Rightarrow a=9.28\quad b=-21.41\quad k=-12.53\quad l=16.61$$ $$t_1=0.67\text{ and }t_2=0.26\Rightarrow a=9.28\quad b=6.42\quad k=12.53\quad l=-20.99$$ En realidad, ambos conjuntos representan el mínimo, pero el primero tiene el sentido inverso al del segundo. La longitud total es $5.25$ . El gráfico siguiente muestra tres curvas. La azul es la primera prueba, la roja la segunda y la verde es el camino óptimo.