In this paper, we investigate the curve simplification problem, where the vertex set of the simplifed curve is a subset of the original curve. To measure the difference between simplified and original curves, we exploit two error metrics: vertical distance, and Frechet distance. In the first case, we develop a fast linear algorithm to approximate the optimal simplifed curve for x-monotone curves within a factor of 2 in the error bound. For Frechet distance metric, we propose an O(n log n) algorithm to approximate the optimal simplified curve for an arbitrary curve not only in 2D, but also in 3-dimensions, within a factor of 4 in the error bound.
Download: | Platform: Sun OS
File size:
Download [AWAITING FILE FROM NABIL] |
Publications: |
"Near-linear time approximation algorithms for curve simplification," P.K. Agarwal, S. Har-Peled, N. Mustafa, and Y. Wang, to appear in Algorithmica.
"Near-linear time approximation algorithms for curve simplification,"
P.K. Agarwal, S. Har-Peled, N. Mustafa, and Y. Wang in Tenth European
Symposium on Algorithms, 2002."
Full text of the paper (pdf) is available here. |
Developers: |
Curve Simplification software was developed
by Nabil Mustafa and Yusu Wang. Contact person is [???] |
Simplification of a Protein (Protein A) backbone: |
|
 |
 |
 |
 |