Longest path among subset of given points

Question

I am looking for an efficient algorithm to solve the following problem:

Given $n$ points in 2D Cartesian space $p_1,\dots,p_n \in \mathbb{R}^2$ and an integer $m$, we want to find $s_1,\dots,s_m$ such that $1 \le s_1 < s_2 < \cdots < s_m \le n$ and that maximizes

$$\sum_{i=1}^{m} \|p_{s_i} - p_{s_{i+1}}\|_2,$$

where $\|p-q\|_2$ represents the $L_2$ distance between two points. In other words, we want to find a subsequence of the points $p_1,\dots,p_n$ such that the distance of following that path is maximized.

Is there an efficient algorithm for this problem?

In my application $m$ is at least 3 orders of magnitude smaller than $n$ and neighboring points $p_i,p_{i+1}$ are close to each other, which makes the search space structured. I have tried simulated annealing with and without an adaptive neighbourhood and get decent results, but I want to know if there is a optimal algorithm. Does anyone know other algorithms and ideally their complexity?

Answer 1

This can be solved exactly with dynamic programming. The running time will be $O(n^2m)$. It finds the exact optimal sequence, not just an approximation.

Let $A[t,u]$ denote the longest path $p_{s_1},\dots,p_{s_t}$ such that $s_t=u$. In other words, it is the maximum possible value of $\|p_{s_1} - p_{s_2}\|_2 + \dots + \|p_{s_{t-1}} - p_{s_t}\|_2$ such that $1 \le s_1 < \cdots < s_t = u$.

Notice that we have a recursive equation that defines $A[\cdot,\cdot]$. In particular,

$$A[t,u] = \max \{ A[t-1,v] + \|p_v - p_u\|_2 : 1 \le v < u\}.$$

Thus, we can fill in the values of $A[t,u]$ incrementally, in order of increasing value of $t$. Each step requires $O(n)$ time, and there are $nm$ entries to fill in, so the total running time is $O(n^2m)$.

In practice the running time might often be something closer to $O(nm)$ if you terminate the search for $v$ early. In the recurrence above you might often be able to prove that if $v$ is much smaller than $u$ the maximum can't be achieved, so you could examine at values of $v$ in decreasing order and stop the iteration early once you know there is no improvement possible with a smaller value of $v$.

Answer 2

[Cannot post a comment with my karma yet, so this has to be an answer.]

If you understand german (or the translation thereof) you might find use in the following link. There are multiple approaches with corresponding explanations, complexity estimations as well as C-code available.

In English, and also somehow related to the answer given by @D.W., consider the seventh post in this thread.

Obviously, none of the ideas above are mine, so I do not intend to take credit for it. May mods convert it to a comment.