1
$\begingroup$

We have a 1D function f(x). We would like to approximate this function with a polyline of n points. How can we find the x position for these points so the polyline approximates f(x) with low error (not necessarily optimal but if it was, then even better)?

What algorithms are available to solve this problem? What are their trade-offs?

Example: the following two polylines have the same number of points but the second one approximates better the curve.

enter image description here

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Take a look at the Ramer–Douglas–Peucker algorithm. $\endgroup$ Commented Dec 30, 2019 at 21:27
  • $\begingroup$ How do you measure error? Mean squared error? $\endgroup$ Commented Dec 31, 2019 at 1:37
  • $\begingroup$ Are the points restricted to be on the curve (as in your example) or can we use endpoints that are off the line if this reduces the overall error? $\endgroup$ Commented Dec 31, 2019 at 1:39
  • $\begingroup$ @Jakube Thanks that's a good one! $\endgroup$ Commented Jan 1, 2020 at 13:09
  • $\begingroup$ @D.W For both questions: any way would work. I don't really have any restrictions in those redards $\endgroup$ Commented Jan 1, 2020 at 13:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.