On the numerical condition of Bernstein-Bézier subdivision processes

Abstract:

The linear map M that takes the Bernstein coefficients of a polynomial $P(t)$ on a given interval [a, b] into those on any subinterval $[\bar a,\bar b]$ is specified by a stochastic matrix which depends only on the degree n of $P(t)$ and the size and location of $[\bar a,\bar b]$ relative to [a, b]. We show that in the ${\left \| \bullet \right \|_\infty }$-norm, the condition number of M has the simple form ${\kappa _\infty }({\mathbf {M}}) = {[2f\max ({u_{\bar m}},{v_{\bar m}})]^n}$, where ${u_{\bar m}} = (\bar m - a)/(b - a)$ and ${v_{\bar m}} = (b - \bar m)/(b - a)$ are the barycentric coordinates of the subinterval midpoint $\bar m = \frac {1}{2}( {\bar a + \bar b} )$, and f denotes the "zoom" factor $(b - a)/(\bar b - \bar a)$ of the subdivision map. This suggests a practical rule-of-thumb in assessing how far Bézier curves and surfaces may be subdivided without exceeding prescribed (worst-case) bounds on the typical errors in their control points. The exponential growth of ${\kappa _\infty }({\mathbf {M}})$ with n also argues forcefully against the use of high-degree forms in computer-aided geometric design applications.