How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm?

Question

Note: I'm a programmer, not a mathematician - please be gentle. I'm not even really sure how to tag this question; feel free to re-tag as appropriate.

I'm using the Douglas-Peucker algorithm to reduce the number of points in polygons (in a mapping application). The algorithm takes a tolerance parameter that indicates how far I'm willing to deviate from the original polygon.

For practical reasons, I sometimes need to ensure that the reduced polygon doesn't exceed a predetermined number of points. Is there a way to predict in advance the tolerance value that will reduce a polygon with N points to one with N' points?

Answer 1

Here is a somewhat nontraditional variation of the Douglas-Peucker algorithm.

We will divide a given curve into pieces which are well approximated by line segments (within tolerance $\varepsilon$). Initially, there is only one piece, which is the entire curve.

1. Find the piece $C$ with the highest "deviation" $d$, where the deviation of a curve is the maximum distance of any point on it from the line segment joining its end points.
2. If $d < \varepsilon$, then all pieces have sufficiently low deviation. Stop.
3. Let $p_0$ and $p_1$ be the end points of $C$, and $q$ be the point on $C$ which attains deviation $d$. Replace $C$ with the piece between $p_0$ and $q$, and the piece between $q$ and $p_1$.
4. Repeat.

It should be easy to see how to modify step 2 so that the algorithm produces exactly $n-1$ pieces, i.e. $n$ points, for any given $n$.

Exercises Things I am too lazy to do myself:

• Show that for (almost) any result of the modified algorithm, there is a corresponding tolerance on which Douglas-Peucker would produce the same result.
• Use priority queues for efficient implementation of step 1.