Speeding Up the Douglas-Peucker Line-Simplification Algorithm

ID
TR-92-07
Authors
John Hershberger and Jack Snoeyink
Publishing date
April 1992
Length
16 pages
Abstract
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.