# Evaluating a 2D cubic Bézier curve with interval coefficients with interval arithmetic

I would like to know how to evaluate 2D cubic Bézier curves at an interval when the Bézier coefficients themselves are intervals.

If the coefficients are not intervals, evaluating a Bézier curve on an interval amounts to computing an axis-aligned bounding box. The $$x$$ and $$y$$ derivatives of a cubic Bézier curve are quadratic polynomials. So, to evaluate a cubic Bézier curve over the interval $$[a,b]$$, we can compute the roots of these derivatives, say getting $$t_{x,1}, t_{x,2}, t_{y,1}, t_{x,2}$$. Discarding those roots that don't lie in $$[a,b]$$, we can evaluate the $$x$$ and $$y$$ components of the Bézier curve at the points $$\{a, t_{x,i}, b\}$$ and $$\{a, t_{y,i}, b\}$$, respectively, and compute the relevant axis-aligned bounding box by taking min&max over these values.

However, I'm not sure how to proceed if the Bézier coefficients are themselves intervals.
Suppose I try the same approach: I can formulate the same quadratic equations, and solve them using interval arithmetic. But this will return a collection of intervals, not a finite set of points. So, then, I have to evaluate the original cubic Bézier at these intervals... but that's precisely the problem I started with! Moreover, the intervals obtained from solving the quadratic equations aren't guaranteed to be smaller than the interval $$[a,b]$$ I started with.

Note that naively evaluating the Bézier curve, using e.g. de Casteljau's algorithm with interval arithmetic, is not a viable option, as it leads to very loose bounds. To illustrate, consider evaluating $$f(t) = t - t^2$$ over $$[0,1]$$. Naively performing interval arithmetic leads to $$[0,1] - [0,1] = [-1,1]$$, when the tightest interval containing $$f([0,1])$$ is actually $$[0,0.25]$$.

Suppose we want to evaluate $$p(t) = \sum_i a_i t^i$$ in interval arithmetic, where $$a_i = [\underline{a_i}, \overline{a_i}]$$ and $$t=[\underline{t}, \overline{t}]$$ are all intervals.

If $$t \geqslant 0$$, then, as $$x \mapsto x^i$$ is monotonically increasing, the minimum value that $$p(t)$$ can reach is the minimum value of $$\underline{p}(t) := \sum_i \underline{a_i} t^i$$, while the maximum value it can reach is the maximum of $$\overline{p}(t) :=\sum_i \overline{a_i} t^i$$.
If $$t \leqslant 0$$, then we proceed similarly, using $$\underline{a_0} + \overline{a_1} t + \underline{a_2} t^2 + \overline{a_3} t^3 + \cdots$$ and $$\overline{a_0} + \underline{a_1} t + \overline{a_2} t^2 + \underline{a_3} t^3 + \cdots$$.
If neither $$t \geqslant 0$$ nor $$t \leqslant 0$$, apply the above logic to the two intervals $$[\underline{t}, 0]$$ and $$[0,\overline{t}]$$.

This reduces the problem of polynomial evaluation to the case of constant (non-interval) coefficients.

For Bézier curves, we can do pretty much the same thing, except now we are using the Bernstein basis

$$b(s) = \sum_i \textrm{B}_i(s) a_i.$$

For $$s \subseteq [0,1]$$, this is a convex combination (the Bernstein polynomials are a partition of unity on $$[0,1]$$), so as long as $$s \subseteq [0,1]$$, we can proceed as in the $$t \geqslant 0$$ case above. If $$s \not \subseteq [0,1]$$, we have to split up the interval and inspect the signs of the Bernstein polynomials (it's straightforward but I haven't needed that generality yet).