How to reduce the number of points in (x,y) data

Question

I have a set of data points:

(x1, y1) (x2, y2) (x3, y3) ... (xn, yn)

The number of sample points can be thousands. I want to represent the same curve as accurately as possible with minimal (lets suppose 30) set of points. I want to capture as many inflection points as possible. However, I have a hard limit on the number of allowed points to represent the data.

What is the best algorithm to achieve the same? Is there any free software library that can help?

PS: I have tried to implement relative slope difference based point elimination, but this does not always result in the best possible data representation.

Thanks for your time.

-Gowtham

Answer 1

it depends on must your curve intersect each point or it is approximation. Try:

1. Take points
2. Apply any interpolation (http://en.wikipedia.org/wiki/Polynomial_interpolation) to get equation of curve
3. Then take sample points with specific step.

Answer 2

Look at ZunZun, an on-line tool.

Answer 3

You are searching for an interpolation algorithm. Is your set of points a function in a mathematical sense (all x values are disjunct from each other) then you can go for a polynomial interpolation, or are they distributed over the 2d plane, then you could use bezier curves.