Line Simplification Literature Review?

Paul Heckbert ph+ at
Tue Jan 30 17:26:24 PST 2001

Steve Zoraster wrote:
> I have not been paying attention to the state-of-the-art in automated 2D
> line simplification for some time. Could someone recommend an up-to-date
> review article on this topic?

If by "line simplification" you mean taking a polyline (piecewise-linear
curve) and approximating it with a new polyline with fewer line segments,
then my survey is relevant:

  Survey of Polygonal Surface Simplification Algorithms,
  Paul S. Heckbert and Michael Garland, tech. report,
  CS Dept., Carnegie Mellon U., 1997,

that is available at

Let me know if you have trouble with the above FTP site.

The survey covers curve simplification briefly.

My high-level conclusions:
 * many literatures have explored this topic, including cartography,
computer graphics, pattern recognition, image processing, computer vision,
computational geometry
 * cartography calls this topic "generalization"
 * there's been a lot of redundant work in this area
 * the Douglas-Peucker algorithm is the most widely-used

Paul Heckbert
Associate Professor
4205 Newell-Simon Hall
Computer Science Dept.
Carnegie Mellon University
Pittsburgh PA 15213-3891, USA

ph at

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list