curvesimp: a near-linear time algorithm for curve simplification

Curve simplification is an important area of research. One of its main uses is in Geographical Information Systems. Geographic Information Systems (GIS) are becoming extremely useful as an analysis tool in science, engineering, environmental and medical research. The use of GIS is made more prominent and useful due to the massive amounts of data made available from satellites and other means. One of main uses of this data is for cartographic purposes, where the information has to be visualized, and presented as a simple, and easily readable map. Since the information is too dense, the maps are usually simplified. For this simplification process, curve simplification is used for simplifying the map piecewise linearly. In this software, we implement a fast algorithm for curve simplification.

  • Near-Linear Time Approximation Algorithms for Curve Simplification. (Pankaj Agarwal, Sariel Har-Peled, Yusu Wang).
    Algorithmica, vol. 42(3), pp. 203-219, 2005.


    You can download the source code here.