# Given a path of 2d points and a maximum distance, find the minimum number of line segments needed to “connect” all points

I have an array of 2 dimensional points describing a path. I want to reduce the number of points needed to describe this path by using line segments that connect multiple points on the same line, allowing for some minimal deviations.

For example, given the points (0,0)-(50,50)-(100,100), the path can be optimized by only specifying (0,0)-(100,100) which will also cover the center point. In case of (0,0)-(49,49)-(100,100) I still want to allow the same line segment of (0,0)-(100,100), as the distance (e.g. euclidian) from the point to the line is small (by a user defined parameter).

What is the minimum number of line segments needed that satisfies the distance condition and how can the segments be determined. Is there a "good" heuristic which is simpler or more efficient while providing comparable results?

## 3 Answers

Try polyline simplification.
For heuristics or other simplifications you might want to treat segments as resizeable, but for now objective is not that clear.
Here is demo of RDP.
Try it, merge your answer into question and then explain objective.

There is tradeoff between polyline complexity reduction and number of remaining points. Number of removed points depends on data and $\epsilon$.

If you want to find minimum, you have $N-1$ segments on $N$ points, and exact reduction depends on colinearity of points. Otherwise it is only approximation.

• Seems like my intuitive solution described in my answer is exactly what RDP does. – aKzenT Sep 10 '15 at 17:43
• Something like that, but the part with minimal number of segments is confusing. – Evil Sep 10 '15 at 17:48
• What I meant is that at some number $N$ of line segments it will be impossible to create a result path which will not violate the rule of no point having a distance larger than $d$. This would be the "simpliest" polyline that satisfies the constraints. I'm not sure that RDP always produces this result. But this is just curiosity, for my application RDP should be good enough. – aKzenT Sep 10 '15 at 17:58
• Please try this RDP heuristic I think it suits better, and the answer to the best (meaning minimal number of segments) is No. – Evil Sep 10 '15 at 18:51
• For short argument - RDP uses local optimization not global, so it cannot guarantee optimal solution. It is used for simplicity and plausible look. If you are happy with answers given, consider accepting ;) – Evil Sep 10 '15 at 18:54

You can use dynamic programming. Define $f(i,k)$ to be the "badness" of the best way to cover points $1..i$ using $k$ line segments. Then you can write down a recurrence relation for $f(i,k)$ in terms of $f(i-1,k-1),\dots,f(1,k-1)$, and then apply dynamic programming.

You'll have to fill in the details, because you haven't provided the particular objective function you specified, but I would expect that this approach will work to find an optimal solution.

Thinking some more about this question, I came up with the following recursive algorithm, which might not produce the minimum, but seems to work very well in practice:

Start by taking the first and last point of the path and treating it as a line segment. Now for each point in between, calculate the distance from this point to the line segment and remember which point has the highest distance. If this distance is smaller than the maximum distance allowed, you are done. Otherwise, split the path at this point by connecting the start and end points to this point and execute the algorithm recursively on the two resulting line segments until all points are within the maximum distance.

I'm happy for better algorithms or thoughts on whether the result is a minimum.