How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm? 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? 
 A: 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.


*

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

*If $d < \varepsilon$, then all pieces have sufficiently low deviation. Stop.

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

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

