Constructing shortest interpolation curve from points in $\mathbb R^2$ with parametric equations.

Question

Assume we are given a set of $n$ points from $\mathbb R^2$, $(x_1,y_1),(x_2,y_2)\dots(x_n,y_n)$.

We want to construct a path connecting all these points using a pair of parametric equations \begin{cases} x = f(t) \\ y = g(t) \\ \end{cases} such that \begin{cases} f(0) = f(1) = x_1 \\ g(0) = g(1) = y_1 \\ \end{cases} and find a set of points $(t_2,t_3\dots t_n),$ for which \begin{cases} f(t_k) = x_k \\ g(t_k) = y_k \\ \end{cases} and the length of the path from $(x_1,y_1)$ to itself via all the other points is minimized.

Now, finding A path is easy. Divide the unit line into $n$ parts, take the starting point of each part to be $t_k$ and construct two interpolation polynomials of degree $n$, $f_p$ and $g_p$, such that $f_p(t_k)=x_k$ and $g_p(t_k)=y_k$ and set \begin{cases} x = f_p(t) \\ y = g_p(t) \\ \end{cases}

Example: Let the original points be $(0,0),(1,1),(2,0)$ and select points of time to be $(1/3,2/3)$. Now the parametric interpolation function is \begin{cases} x = -\frac{27}{2} (-1 + t) t^2 \\ y = \frac{9}{2} (-1 + t) t (-2 + 3 t) \\ \end{cases}

The length of this path is acquired via formula $L=\int_0^1 \sqrt{{\frac{dx}{dt}}^2+{\frac{dy}{dt}}^2} dt$ and it is approximately $5.422$.

However, if we select times to be $(1/4,3/4),$ we get function \begin{cases} x = -\frac{8}{3} (-1 + t) t (1 + 4 t) \\ y = \frac{8}{3} (-1 + t) t (-3 + 4 t) \\ \end{cases} and the length is now approximately $5.411$.

Thus optimizing the length of the path requires two components, selecting the times $t_k$ and also selecting the original interpolation functions. The times can be optimized via normal differentiation methods, but how can we optimize over the interpolation functions? The method for solving this type of problem is calculus of variations. Can it be applied into this type of problem with interpolation and parametric equations?

This is some kind of "continuous" variant of the travelling salesman problem and I was hoping maybe I could get some faster, more robust methods for solving TSP in general from this, but looking at the simplest of examples, I notice that both the interpolation functions and the required integrations become exceedingly complex very fast. So is there some methods for simplifying the process?

Edit: Is there a quick way to get good selection of $t_k$s?

Answer 1

You want to construct n-degree polynomial for n points. In your example take the functions as $$x(t)=at^3+bt^2+ct+d$$ $$y(t)=kt^3+lt^2+mt+n$$ The first condition $x(0)=y(0)=0$ requires that $d=n=0$. Your second condition $x(1)=y(1)=0$ can be satisfied if $c=-(a+b)$ and $m=-(k+l)$ $$\Rightarrow x(t)=at^3+bt^2-(a+b)t$$ $$\Rightarrow y(t)=kt^3+lt^2-(k+l)t$$ Now a simplification can be done for integral. We can minimize $\int f(t)\,dt$ instead of $\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}$$ Now you must impose interior conditions. For $x(t)$ it follows that $$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}}$$ For $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}}$$ Now we can replace $a,b,k,l$ as functions of $t_1,t_2$. To minimize the integral we use first derivatives $$\frac{\partial I}{\partial t_1}=\frac{\partial I}{\partial t_2}=0$$ Solving the above system gives following solution sets $$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$$ Actually both sets represent the minimum but the first one has the reverse direction as of second one. Total length is $5.25$. Below graph shows three curves. Blue one is your first trial; red one your second and the green one is the optimal path.