approximate non-linear transformation of affine combination

Considerapplying an arbitrary transformation $f$to an affine combination ${\sum }_{i=1}^n{w}_i{x}_i$of some points $x_i$,with non-negative weights $w_i$ that sum to unity.Obviously, in general,

$$f\left(\sum _{i=1}^n{w}_i{x}_i\right)\ne \sum _{i=1}^n{w}_{i}f(x_i).$$

However, sometimes it is desirable to compute the image$f({\sum }_i{w}_i{x}_i)$as if $f$ were a linear (or affine) transformation;the result is then hoped to be a good approximationto the true value.(See below for an application.)

Actually, it is possible to show that, provided that $f$ is twicecontinuously differentiable, the approximation is good to first order,despite the absence of any derivatives of $f$ in the formula.The domain and range of $f$ may be any normed vector spaces.

First, we write:

$f\left({\displaystyle \sum _i}{w}_i{x}_i\right)$$=f\left({\displaystyle \sum _i}{w}_i(x_i-x_1)+x_1\right)$

$=f(x_1)+{\displaystyle \sum _i}{w}_i{f}^{\prime }(x_1)(x_i-x_1)+O\left({\parallel {\displaystyle \sum _i}{w}_i(x_i-x_1)\parallel }^2\right).$

If $h={\max }_i\parallel x_i-x_1\parallel$,then $\parallel {\sum }_i{w}_i(x_i-x_1)\parallel \le {\sum }_i|w_i|h=h$,and so the error term in the Taylor expansioncan be simplified to $O(h^2)$.

Substituting another Taylor expansion

$f(x_i)-f(x_1)=f^{\prime }(x_1)(x_i-x_1)+O(h^2),$

into the first, we obtain:

$f\left({\displaystyle \sum _i}{w}_i{x}_i\right)$$=f(x_1)+{\displaystyle \sum _i}{w}_i\left(f(x_i)-f(x_1)+O(h^2)\right)+O(h^2)$

$={\displaystyle \sum _i}{w}_{i}f(x_i)+O(h^2).$

Furthermore, it is not hard to see,by accounting the error from the Taylor expansions more carefully,that we have the bound:

$$\parallel f\left(\sum _i{w}_i{x}_i\right)-\sum _i{w}_{i}f(x_i)\parallel \le M{h}^2,$$

where $M$ is the maximum,as $\xi$ ranges inside the convex hullformed by the points $x_i$,of the quantity $\parallel f^{\prime \prime }(\xi )\parallel =\underset{u\ne 0}{sup}\frac{\parallel f^{\prime \prime }(\xi )(u,u)\parallel }{{\parallel u\parallel }^2}$.Finally, the point $x_1$ over which we performed Taylor expansionscan be replaced by any other point $x_k$,and so correspondingly $h$ can be replaced by ${\min }_k{\max }_i\parallel x_i-x_k\parallel$.

Application in computer graphics

The principle just derived is often applied in vector-based computer graphicswhen curved objects are drawn by cubic Bézier curves:

$$\gamma (t)=\sum _{i=0}^3{w}_i(t)x_i,w_i(t)=\left(\genfrac{}{}{0pt}{}{3}{i}\right){(1-t)}^{n-i}{t}^i,$$

which are affine combinations of the control points $x_i$.To compute and display a smooth transformation $f$ of such curves,it may be too much work to compute $f(\gamma (t))$ repeatedlyfor many parameter values $t$.Provided $\gamma$ is not too wavy,computing and displaying ${\sum }_{i=0}^3{w}_i(t)f(x_i)$is vastly more efficient, and may result in little orno visually perceptible difference.

As a concrete example, consider bending a straight line segmentinto a circle.Mathematically, we are mapping the interval $[0,2\pi ]$via $t\mapsto (r\cos t,r\sin t)$.If the interval is split into sub-segments,each considered as acubic Bézier curve with its interior control pointsboth set at the midpoint of the line segment,then a circle can be approximatedby transforming these control points.The following diagram shows the approximation for 24 segments (three Béziercurves per ${45}^{\circ }$ arc).

Figure 1: Circle drawn using approximate mapping of line segment