Line Simplification Literature Review?

[Paul Heckbert]

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

 
ftp://ftp.cs.cmu.edu/afs/cs/project/anim/ph/paper/multi97/release/intro.html#contents

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 cs.cmu.edu
http://www.cs.cmu.edu/~ph

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.