1
$\begingroup$

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?

$\endgroup$
1
+50
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

[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.

$\endgroup$
  • 1
    $\begingroup$ Can you edit your answer to summarize the main ideas found at those links? We don't want to be just a link farm; we want to have useful content of our own here. Also, if the links stop working, this answer becomes useless. Summarizing the main ideas there, so this answer can stand on its own, would make this a suitable answer. $\endgroup$ – D.W. Jan 6 '18 at 18:58
  • $\begingroup$ Understood. I will do my best. Expect editied answer within a week. $\endgroup$ – lactea Jan 6 '18 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.