How to Prove Division of One Bezier Curve into Two using de Casteljau Algorithm

Question

$\newcommand{\brstbasis}[2]{b^{#1}_{#2}}$ $\newcommand{\posintset}{\mathbb{Z}^{+}}$ $\newcommand{\intset}{\mathbb{Z}}$ $\newcommand{\realset}{\mathbb{R}}$ $\newcommand{\domain}[1]{\operatorname{dom}\left(#1\right)}$

To provide background for this proof, first we define De Casteljau coefficients. Let $n \in \posintset$ and $p$ be a sequence of size $n + 1$ and $\tau \in \left(0, 1\right)$. We say $c$ is a deCateljau function of $p$ with respect to $\tau$ if and only if $c$ is a function such that $\domain{c} = \intset \times \intset$ and for any $i, j \in \intset$, \begin{equation} c\left(i, j\right) = \begin{cases} p_{i},\ 0 \leq i \leq n \wedge j = 0\\ 0,\ i < 0 \vee i > n \vee \left(0 \leq i \leq n \wedge \left(j < 0 \vee j > i\right)\right)\\ \left(1 - \tau\right) c\left(i - 1, j - 1\right) + \tau c\left(i, j - 1\right),\ \textrm{otherwise}. \end{cases} \end{equation}

De Casteljau Algorithm has two parts, one is for evaluation of a Bezier curve at an arbitrary point $t \in \left[0, 1\right]$, while the other one is to divide a Bezier curve into two using the same set of Bernstein bases.

The first part can be summarized as follows. Let $n \in \posintset$, $p$ be a sequence of $n + 1$ points, $r$ be a Bezier curve such that for any $t \in \left[0, 1\right]$, \begin{equation*} r\left(t\right) = \sum_{k=0}^{n} p_{k} \brstbasis{n}{k}\left(t\right). \end{equation*} Also, let $\tau \in \left(0, 1\right)$ and $c$ be the de Casteljau coefficients of $p$ with respect to $\tau$. Then for any $i, j \in \intset$, if $0 \leq j \leq n$ and $j \leq i \leq n$, then \begin{equation*} c\left(i, j\right) = \sum_{k=0}^{j}p_{i - j + k} \brstbasis{j}{k}\left(\tau\right). \end{equation*} In particular, \begin{equation*} c\left(n, n\right) = \sum_{k=0}^{n} p_{k} \brstbasis{n}{k}\left(\tau\right) = r\left(\tau\right). \end{equation*}

I have proved the first part using mathematical induction, and I am stuck on proving the second part. The second part can be summarized as follows. Let $n \in \posintset$, $p$ be a sequence of $n + 1$ points, $r$ be a Bezier curve such that for any $t \in \left[0, 1\right]$, \begin{equation*} r\left(t\right) = \sum_{k=0}^{n} p_{k} \brstbasis{n}{k}\left(t\right). \end{equation*} Also, let $\tau \in \left(0, 1\right)$ and $c$ be the de Casteljau coefficients of $p$ with respect to $\tau$. Further, let $\Gamma$ and $\Psi$ be sets of points of the two partitions of $r$ such that \begin{equation*} \Gamma = \left\{x \in \realset \vert x = r\left(t\right) \textrm{ for some } t \in \left[0, \tau\right]\right\} \end{equation*} and \begin{equation*} \Psi = \left\{x \in \realset \vert x = r\left(t\right) \textrm{ for some } t \in \left[\tau, 1\right]\right\}, \end{equation*} $\alpha$ and $\beta$ be Bezier curves such that for any $t \in \left[0,1\right]$, \begin{equation*} \alpha\left(t\right) = \sum_{i=0}^{n} c\left(i, i\right) \brstbasis{n}{i}\left(t\right) \end{equation*} and \begin{equation*} \beta\left(t\right) = \sum_{i=0}^{n} c\left(n, n - i\right) \brstbasis{n}{i}\left(t\right), \end{equation*} and $S$ and $T$ are points of $\alpha$ and $\beta$ such that \begin{equation*} S = \left\{x \in \realset \vert x = \alpha\left(t\right) \textrm{ for some } t \in \left[0, 1\right]\right\} \end{equation*} and \begin{equation*} T = \left\{x \in \realset \vert x = \beta\left(t\right) \textrm{ for some } t \in \left[0, 1\right]\right\}. \end{equation*} Then $\Gamma = S$ and $\Psi = T$.

I am trying to use mathematical induction to prove the second part. Let $P$ be the predicate such that for any $n \in \posintset$, $P\left(n\right)$ if and only if the statement holds for $n$.

First we examine $P\left(0\right)$. In this case, for any $t \in \left[0, 1\right]$, $r\left(t\right) = p_{0}$. Then $\Gamma = \left\{p_{0}\right\}$ and $\Phi = \left\{p_{0}\right\}$. Further, by \cref{def: de casteljau coefficients}, $c\left(0, 0\right) = p_{0}$. Then for any $t \in \left[0,1\right]$, $\alpha_{t} = p_{0}$ and $\beta_{t} = p_{0}$. Consequently, $S = \left\{p_{0}\right\}$ and $T = \left\{p_{0}\right\}$. Finally we have $\Gamma = S$ and $\Phi = T$.

Next, let $n \in \posintset$ and assume that $P\left(n\right)$. It is our desire to prove $P\left(n + 1\right)$. Let $\tau \in \left(0, 1\right)$, $p$ be a sequence of $n + 2$ points, $c$ be the de Casteljau coefficients of $p$. Further, let $r$ be a Bezier curve such that \begin{equation*} r\left(t\right) = \sum_{k=0}^{n + 1} p_{k} \brstbasis{n + 1}{k}\left(t\right), \end{equation*} $\Gamma$ and $\Psi$ be partitions of $r$ such that \begin{equation*} \Gamma = \left\{x \in \realset \vert x = r\left(t\right) \textrm{ for some } t \in \left[0, \tau\right]\right\}, \end{equation*} and \begin{equation*} \Psi = \left\{x \in \realset \vert x = r\left(t\right) \textrm{ for some } t \in \left[\tau, 1\right]\right\}. \end{equation*} Further, let $\alpha$ and $\beta$ be Bezier curves such that for any $t \in \left[0,1\right]$, \begin{equation*} \alpha\left(t\right) = \sum_{i=0}^{n + 1} c\left(i, i\right) \brstbasis{n + 1}{i}\left(t\right) \end{equation*} and \begin{equation*} \beta\left(t\right) = \sum_{i=0}^{n + 1} c\left(n + 1, n + 1 - i\right) \brstbasis{n + 1}{i}\left(t\right). \end{equation*} Also, let $S$ and $T$ be sets such that \begin{equation*} S = \left\{x \in \realset \vert x = \alpha\left(t\right) \textrm{ for some } t \in \left[0, 1\right]\right\} \end{equation*} and \begin{equation*} T = \left\{x \in \realset \vert x = \beta\left(t\right) \textrm{ for some } t \in \left[0, 1\right]\right\}. \end{equation*} It is our desire to prove that $S = \Gamma$ and $T = \Psi$.

By the theorem from the first part, for any $i \in \left[0, n + 1\right] \cap \posintset$, \begin{equation*} c\left(i, i\right) = \sum_{k=0}^{i} p_{k} \brstbasis{i}{k}\left(\tau\right) \end{equation*} and \begin{equation*} c\left(n + 1, n + 1 - i\right) = \sum_{k=0}^{n + 1 - i} p_{i + k} \brstbasis{n + 1 - i}{k}\left(\tau\right). \end{equation*} Then \begin{equation*} \begin{aligned} \alpha\left(t\right) &= \sum_{i=0}^{n + 1} c\left(i, i\right) \brstbasis{n + 1}{i}\left(t\right) = \sum_{i=0}^{n + 1} \left(\sum_{k=0}^{i} p_{k} \brstbasis{i}{k}\left(\tau\right)\right) \brstbasis{n + 1}{i}\left(t\right) \end{aligned} \end{equation*} and \begin{equation*} \beta\left(t\right) = \sum_{i=0}^{n + 1} c\left(n + 1, n + 1 - i\right) \brstbasis{n + 1}{i}\left(t\right) = \sum_{i=0}^{n + 1} \left(\sum_{k=0}^{n + 1 - i} p_{i + k} \brstbasis{n + 1 - i}{k}\left(\tau\right)\right) \brstbasis{n + 1}{i}\left(t\right) \end{equation*}

I am not sure if I am on the right track. Ideally, I should somehow find a way to utilize $P\left(n\right)$. Can anyone help me sort out the path for proof?

Answer 1

The easiest proof is probably via blossoming. Given a polynomial $f$ of degree $m$, there is a unique symmetric mult-affine function $F$ of $m$ variables such that $F(x, \ldots, x) = f(x)$ for all $x$. We call $F$ the blossom or polar form of $f$.

In some sense, the blossom is just a very clever way to label the points that show up in the de Casteljau algorithm. Let’s take the cubic case, to be specific. There is a theorem that says that the Bézier control points of the curve $f$ on the interval $[a,b]$ are just $F(a,a,a)$, $F(a,a,b)$, $F(a,b,b)$, $F(b,b,b)$.

If you use the de Casteljau algorithm to divide this curve segment at $c \in [a,b]$, then you will find (by virtue of the multi-affine property of $F$) that it generates the points $F(a,a,a)$, $F(a,a,c)$, $F(a,c,c)$, $F(c,c,c)$ and $F(c,c,c)$, $F(c,c,b)$, $F(c,b,b)$, $F(b,b,b)$. These are precisely the Bézier control points of the curve segments on the intervals $[a,c]$ and $[c,b]$.

For more details, lookup “blossoming of Bézier curves”.