7. Computational Algorithms

As we mentioned in Chapter 1, algorithms for computing spline functions may be classified into three types. For multivariate splines s(x) that satisfy some recurrence relationship, such as the box splines as given by (2.6) in Theorem 2.5, the user can compute s(x) exactly for each fixed x using the recurrence relationship and compute s(y) again for another value of y. The second type is to give an efficient approximation scheme which is based on another recurrence relationship. This type is very useful for graphic display purposes. The third type is to give an explicit representation, say in terms of the Bézier net, of each polynomial piece. Algorithms of this type depend on yet another form of recurrence relationship. In this chapter, we will not go into the first type of algorithm, but discuss briefly a representative algorithm of each of the latter two types. We first consider a simple technique for displaying a polynomial “surface.”