Bounded error
© 16 September 2021 Luther Tychonievich
Licensed under Creative Commons: CC BY-NC-SA 3.0
other posts

Why Bézier curves are magically special.

 

Mathematics can be divided into continuous mathematics, where there are numbers between any pair of numbers you happen to pick, and discrete mathematics, where there is not.

Continuous mathematics often deals in functions defined by formulae. For example, you’ve likely seen a function definition such as f(x) = 3.2x + 2.1 in the past. But often overlooked in introductions to functions like this is that we don’t know continuous numbers to precision.

Let’s suppose we only know the numbers involved in f(x) = 3.2x + 2.1 with once decimal place of precision. In other words, when we say 3.2, we might mean 3.1501 or 3.2499 or anything in between. With this assumption, let’s consider f(20) = 3.2 ⋅ 20 + 2.1. Let’s try it out at a few different possible values:

Note that the error in the answer is a lot larger than the error we started with; we initially knew the numbers to within ±0.05 but after using the function we know them only to within ± 1.0. This magnification of errors will increase both as x gets farther from 0 and as we use more complicated functions.

However, this is a magical way of defining lines that doesn’t have this problem: using two points. The same line given by f(x) = 3.2x + 2.1 can also be defined as “‍the line that connects (−10.0, −29.9) and (100.0, 322.1)‍”. We’ll formalize this in a formula as a weighted average: f(x) = −29.9
100−x
100−(−10)
+ 322.1
x−(−10)
100−(−10)
Let’s try it out at a few different possible values:

Notice that resulting error is bounded to exactly the same range as the input error. That will be true everywhere between those two points. However, go beyond them and the error grows again:

Thus, if we know the maximum extent we want to evaluate a line over, we are better off storing the endpoints of the line instead of its slope and intercept.

We might also ask, can we do something similar for more complicated functions? In 1912 Sergei Bernstein showed that at least for polynomials, the answer is yes, though his analysis was not posed in terms of points or error. In the 1960s Pierre Bézier showed a generalization of Bernstein’s polynomials and expressed them in terms of points, paving the way for them being used in computers and their error behavior being analyzed.

Bézier curves are often expressed as an artist-friendly way of specifying parametric curves, and they are that; but they are also one of very few computations that do not magnify the error they are given.




Looking for comments…



Loading user comment form…