Box splines.

*(English)*Zbl 0814.41012
Applied Mathematical Sciences. 98. New York, NY: Springer-Verlag. xvii, 200 p. (1993).

From the authors’ preface: Compactly supported smooth piecewise polynomial functions provide an efficient tool for the approximation of curves and surfaces and other smooth functions of one and several arguments. Since they are locally polynomial, they are easy to evaluate. Since they are smooth, they can be used when smoothness is required, as in the numerical solution of partial differential equations (in the finite element method) or the modeling of smooth surfaces (in computer aided geometric design). Since they are compactly supported, their linear span has the needed flexibility to approximate at all, and the system to be solved in the construction of approximations are ‘banded’.

The construction of compactly supported smooth piecewise polynomials becomes ever more difficult as the dimension, \(s\), of their domain \(G\subseteq R^ s\), i.e. the number of arguments, increases. In the univariate case, there is only one kind of cell in any useful partition, namely, an interval, and its boundary consists of two separated points, across which polynomial pieces would have to be matched as one constructs a smooth piecewise polynomial function. This can be done easily, with the only limitation that the number of smoothness conditions across such a breakpoint should not exceed the polynomial degree (since thay would force the two joining polynomial pieces to coincide). In particular, on any partition, there are (nontrivial) compactly supported piecewise polynomials of degree \(\leq k\) and in \(C^{(k -1)}\), of which the univariate B-spline in the most useful example. However, when \(s>1\), then a useful partition may contain cells of various types (simplices and perturbations of parallelepipeds being the most common), and the boundary of a cell is not connected, but becomes an ever more important part of a cell as \(s\) increases (since its dimension differs from that of the cell itself only by 1). This makes the construction of low-degree compactly supported smooth piecewise polynomials impossible except on very special partitions.

In fact, for \(s>1\), the only general construction principle presently available is that of the so-called polyhedral splines (a.k.a. ‘multivariabe B-splines’), of which the box spline, the simplex spline, and the cone spline are the most striking examples. These are obtained as the \(s\)-dimensional ‘shadow’ of an \(n\)-dimensional polytope (e.g. the standard \(n\)-cube, the standard \(n\)-simplex, or the positive \(n\)- orthant), are piecewise polynomial of degree \(\leq n-s\), with support equal to the corresponding projection of the polytope into \(R^ s\), and are in \(C^{(n -s-1)}\) if the projector used is generic. In any case, since their partition is determined by just how the \(n\)-dimensional polytope is projected into \(R^ s\), it is usually not possible to prescribe the partition (in line with the fact that, for a generic partition, there are no compactly supported piecewise polynomials of degree \(k\) in \(C^{(\rho)}\) for \(\rho\) close to \(k\)). However, it is possible to refine any triangulation to a partition for which sufficiently many (translated) smooth simplex splines are available to span a piecewise polynomial space of good approximation power. Alternatively, if the given partition is sufficiently uniform, then there are box splines available whose integer translates span a space of piecewise polynomials with that partition of good approximation power. Such spaces are the multivariate equivalent of the univariate cardinal spline studied intensively by I. J. Schoenberg and others.

As with Schoenberg’s cardinal spline, box splines give rise to an intriguing and beautiful mathematical theory, much more intricate and rich, hence less complete at present. The basic facts, however, have been available for several years, albeit in various papers only, several of these papers are quite long, and are more devoted to the publication of specific new results than to a careful exposition of the theory. We wrote this book to remedy this. We have not merely organized the available material in some cohesive way, but have also, looked quite carefully at the available arguments and, in many cases, modified them considerably, in line with our goals to provide simple and complete proofs.

While we have endeavored to provide an up-to-date bibliography of papers concerned with box splines, we have made no attempt to report here anything more than what we consider to be the basic box spline theory. In particular, we have included nothing about spaces generated by several box splines, since their theory is far from complete at present. Neither have we dealt with the promising theory of exponential box splines.

The book is organized in the following way. In chapter I, we give the various equivalent definitions of a box spline, and derive its basic properties, we urge the readers unfamiliar with box splines to read ahead to the various detailed (bivariate) examples (and construct others of their own). The rest of the book is concerned with various aspects of the principle shift-invariant space generated by a box spline (a.k.a. a cardinal spline space). For this reason, only box splines with integer directions are considered after chapter I. The linear algebra of a cardinal spline space is the topic of chapter II. It highlights the results of Dahmen and Micchelli on linear independence and the kernels of certain related differential and difference operators. Chapter III brings the basic results on approximation order from a box spline space, and includes a discussion of the construction of quasi-interpolants which realize this order. In chapter IV, Schoenberg’s beautiful theory of cardinal spline interpolation is discussed in the setting of box splines where it becomes necessary to devote much more effort to the singular case than in the univariate setting. Chapter V begins with a discussion of the convergence of cardinal splines as their degree tends to infinity and continues with the natural relation of cardinal splines to the multivariate Whittaker cardinal series and wavelets. The theory of discrete box splines is developed in chapter VI in close analogy to that of the (continuous) box spline. It provides the basic for the discussion of subdivision algorithms for the generation of box splines surfaces, in the final chapter.

The construction of compactly supported smooth piecewise polynomials becomes ever more difficult as the dimension, \(s\), of their domain \(G\subseteq R^ s\), i.e. the number of arguments, increases. In the univariate case, there is only one kind of cell in any useful partition, namely, an interval, and its boundary consists of two separated points, across which polynomial pieces would have to be matched as one constructs a smooth piecewise polynomial function. This can be done easily, with the only limitation that the number of smoothness conditions across such a breakpoint should not exceed the polynomial degree (since thay would force the two joining polynomial pieces to coincide). In particular, on any partition, there are (nontrivial) compactly supported piecewise polynomials of degree \(\leq k\) and in \(C^{(k -1)}\), of which the univariate B-spline in the most useful example. However, when \(s>1\), then a useful partition may contain cells of various types (simplices and perturbations of parallelepipeds being the most common), and the boundary of a cell is not connected, but becomes an ever more important part of a cell as \(s\) increases (since its dimension differs from that of the cell itself only by 1). This makes the construction of low-degree compactly supported smooth piecewise polynomials impossible except on very special partitions.

In fact, for \(s>1\), the only general construction principle presently available is that of the so-called polyhedral splines (a.k.a. ‘multivariabe B-splines’), of which the box spline, the simplex spline, and the cone spline are the most striking examples. These are obtained as the \(s\)-dimensional ‘shadow’ of an \(n\)-dimensional polytope (e.g. the standard \(n\)-cube, the standard \(n\)-simplex, or the positive \(n\)- orthant), are piecewise polynomial of degree \(\leq n-s\), with support equal to the corresponding projection of the polytope into \(R^ s\), and are in \(C^{(n -s-1)}\) if the projector used is generic. In any case, since their partition is determined by just how the \(n\)-dimensional polytope is projected into \(R^ s\), it is usually not possible to prescribe the partition (in line with the fact that, for a generic partition, there are no compactly supported piecewise polynomials of degree \(k\) in \(C^{(\rho)}\) for \(\rho\) close to \(k\)). However, it is possible to refine any triangulation to a partition for which sufficiently many (translated) smooth simplex splines are available to span a piecewise polynomial space of good approximation power. Alternatively, if the given partition is sufficiently uniform, then there are box splines available whose integer translates span a space of piecewise polynomials with that partition of good approximation power. Such spaces are the multivariate equivalent of the univariate cardinal spline studied intensively by I. J. Schoenberg and others.

As with Schoenberg’s cardinal spline, box splines give rise to an intriguing and beautiful mathematical theory, much more intricate and rich, hence less complete at present. The basic facts, however, have been available for several years, albeit in various papers only, several of these papers are quite long, and are more devoted to the publication of specific new results than to a careful exposition of the theory. We wrote this book to remedy this. We have not merely organized the available material in some cohesive way, but have also, looked quite carefully at the available arguments and, in many cases, modified them considerably, in line with our goals to provide simple and complete proofs.

While we have endeavored to provide an up-to-date bibliography of papers concerned with box splines, we have made no attempt to report here anything more than what we consider to be the basic box spline theory. In particular, we have included nothing about spaces generated by several box splines, since their theory is far from complete at present. Neither have we dealt with the promising theory of exponential box splines.

The book is organized in the following way. In chapter I, we give the various equivalent definitions of a box spline, and derive its basic properties, we urge the readers unfamiliar with box splines to read ahead to the various detailed (bivariate) examples (and construct others of their own). The rest of the book is concerned with various aspects of the principle shift-invariant space generated by a box spline (a.k.a. a cardinal spline space). For this reason, only box splines with integer directions are considered after chapter I. The linear algebra of a cardinal spline space is the topic of chapter II. It highlights the results of Dahmen and Micchelli on linear independence and the kernels of certain related differential and difference operators. Chapter III brings the basic results on approximation order from a box spline space, and includes a discussion of the construction of quasi-interpolants which realize this order. In chapter IV, Schoenberg’s beautiful theory of cardinal spline interpolation is discussed in the setting of box splines where it becomes necessary to devote much more effort to the singular case than in the univariate setting. Chapter V begins with a discussion of the convergence of cardinal splines as their degree tends to infinity and continues with the natural relation of cardinal splines to the multivariate Whittaker cardinal series and wavelets. The theory of discrete box splines is developed in chapter VI in close analogy to that of the (continuous) box spline. It provides the basic for the discussion of subdivision algorithms for the generation of box splines surfaces, in the final chapter.

Reviewer: E.Deeba (Houston)

##### MSC:

41A15 | Spline approximation |