The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Douglas-Peucker line simplification algorithm implementation by Jack Snoeyink

DPsimp is a Douglas-Peucker line simplification alogorithm implementation by John Hershberger and Jack Snoeyink. They 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. The algorithm is based on path hulls, that uses the geometric structure of the problem to attain a worst-case running time proportional to nlog_2(n), which is the best case of the Douglas algorithm. Complete C code is given and the two algorithms are compared theoretically, by operation counts, and practically, by machine timings.

  • Download Files (local site)
  • Jack Snoeyink's site
  • Link to source file

    Problem Links

    Simplifying Polygons (8)

    This page last modified on 2008-07-10 .