Sort a set of points to minimize the sum of the square distances between two consecutive points

227 Views Asked by At

Let $P$ be a finite set of points in $\mathbb{R}^3$. Let the number of points in $P$ be $n\in\mathbb{N}$. I want to sort the points in $P$ to minimize the sum of the distances between two consecutive points:

\begin{align} &\text{minimize} &&\sum_{i=1}^{n-1} ||p_i-p_{i+1}||^2\\ &\text{subject to} && p_i\in P \end{align}

Any sorting algorithm that I have looked up refers to sorting a set of scalar values, from smallest to biggest.