Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

Multivariate Splines and the 4 Color Map Problem





Notes

V B is the number of boundary vertices of the triangulations, and V I the number of interior vertices.

The simplest example of a non-generic triangulation is formed by a singular vertex.

It's an open problem whether every non-degenerate triangulation is generic. Not every degenerate triangulation is non-generic.

The major feature that distinguishes bivariate splines from univariate splines (which are functions of just one independent variable) is that the dimension depends not just on the number of triangles and how they are connected, but also on the precise location of the vertices. By contrast, in the univariate case it suffices to specify the number N of subintervals, the degree r of smoothness, and the polynomial degree d to determine the dimension of Srd (in fact, it's d+1+(N-1)(d-r) ). In the bivariate case an arbitrarily small change in the location of one vertex can cause the dimension of the spline space to change!

However, for every topology of the triangulation (which describes how triangles are connected) there is a generic dimension. If the spline space does not have that dimension then there is an arbitrarily small perturbation of the location of the vertices that will cause the dimension to assume that generic value. Moreover, the generic dimension is always the smallest possible dimension.

This is actually easy to see by a beautiful and simple argument: Express the polynomials on each triangle as a linear combination of basis functions, e.g., in the power form. Then write down the differentiability conditions. These form a set of homogeneous linear equations. The dimension of the spline space equals the number of the available coefficients minus the rank of the system of smoothness conditions. Now consider a set of vertices that causes the matrix of that linear system to have the largest rank (and the spline space the smallest dimension) possible. Pick a largest possible non-singular square submatrix of that linear system. Its determinant is non-zero, and it is a rational function of the locations of the vertices. Think of those n locations as one point in 2n dimensional space. The determinant can vanish only on a set of vertex locations of measure zero, and if it does vanish the vertex vector can be moved out of that set by an arbitrarily small movement.

Billera investigated the spline problem using methods from algebraic homology that led to a particular linear system based on cofactors. Whiteley analyzed that system using methods from rigidity theory.

These ideas are summarized, and then applied to trivariate splines, in a paper by Larry Schumaker, Walter Whiteley, and myself:

The generic dimension of the space of C1 splines of degree d >= 8 on tetrahedral decompositions, SIAM JNA, v. 30, pp. 889--920, 1993.

Click here to view a dvi file or a postscript file of the paper.

[21-Apr-1997]