Efficient way to find key points on spline to approximate it with line strip Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the line strip and the spline at any given point is &lt;= d.
Here is a visual example. I'm looking to find a computationally efficient way to find the points in the green circles that I use as beginnings and endings for the lines.

What I thought about is walking along the spline, summing up the traveled distance. As I walk the spline, I test the last position as a key-point candidate. Once the distance traveled on the spline and the length of the line through the key-point candidate deviate by a certain percentage, I use the last key point candidate that was still below that percentage. What I'm uncertain about is first, if there is a more efficient way, and second, deviation in length as a percentage is not really the same as distance (e.g. in cm). If there is a relatively long, relatively straight part of the spline, the length deviation that I might accept, could lead to quite a large distance between the spline and the line somewhere on the way, couldn't it?
[Discussion / Comments]
What's a &quot;line strip&quot;?
For the purpose of this question a line strip is a bunch of connected line segments, like the red strip in the image above.
Do you require that each endpoint of each line segment in the line strip must be on the spline?
No. I just require that the maximum distance between the line segment and the spline segment is &lt;= d. And I want to end up with a small number of line segments. It doesn't need to be the smallest number possible, but it should be reasonably small. The smaller the better. If allowing for a few extra segments prevents me from having to iterate over my solutions for optimization, I'd take that.
Given the difference between the lengths of the curved and straight segments, you can give an upper bound for maximal distance between them
That is not a bad idea! As I stated above, I tried this by giving the deviation in percent of the line-segment's length. But using the absolute deviation in length instead (without converting to percent), does give me an upper bound for the maximum distance. So this would be better than what I used before.
A simple approach would be to take a dense sample of points on the spline (i.e., more than you need), and then apply the Ramer-Douglas-Peucker polyline simplification algorithm to get rid of as many of them as possible. Note: Unless you generate the point sample in some clever way (e.g., with density proportional to the local curvature), this isn't guaranteed to recover sharp bends perfectly.
According to that Wikipedia page, the straightforward implementation takes $O(n^2)$ time in the worst case for $n$ points, though there is also a more complicated version due to Hershberger and Snoeyink that takes just $O(n \log n)$ time in the worst case.