Technical Reports

The ICICS/CS Reading Room


UBC CS TR-92-07 Summary

Speeding Up the Douglas-Peucker Line-Simplification Algorithm, April 1992 John Hershberger and Jack Snoeyink, 16 pages

We analyze the line simplification algorithm reported by Douglas and Peucker and show that its worst case is quadratic in n, the number of input points. Then we give a algorithm, based on path hulls, that uses the geometric structure of the problem to attain a worst-case running time proportional to n log_2(n), which is the best case of the Douglas algorithm. We give complete C code and compare the two algorithms theoretically, by operation counts, and practically, by machine timings.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.