Bivariate Splines and the Four Color Map Problem
This map of the United States was colored by Barrett Walls,
in a project with
Daniel P. Sanders,
Paul Seymour and
Reproduced with permission.
The Four Color Map Problem
Four Color Map Theorem
states that any map in the plane or on the sphere can be colored
with only four colors such that no two neighboring countries are
of the same color. The problem has a long history and inspired
many people (including many non-mathematicians and in
particular countless high school students) to attempt a
solution. The question of whether four colors always suffice
was first stated in 1852 by Francis Guthrie and remained
unanswered until Appel and Haken came up with a book length
proof in 1976.
Multivariate Splines are smooth piecewise polynomial functions
defined on a suitable tessellation of a two or three-dimensional
domain. They have been my primary area of research since 1984.
Probably the most famous open problem in multivariate splines is
the question of a simple formula for the dimension of a
particular spline space. Consider a
i.e., a tessellation of a polygonal domain by triangles
(satisfying certain technical requirements). The splines of
interest here are once differentiable everywhere on the domain,
and they can be represented on each triangle as a polynomial (in
two variables) of degree 3. The space of these splines is of
great practical interest since it offers the possibility of
interpolating to function values at the vertices of the
triangles with the smallest possible polynomial degree.
The spline problem appears to be extremely difficult. The
reason for its still open status is not a lack of trying! The
reason for the difficulty is the same as the reason for the
difficulty of the four color map problem: it is hard to
localize things! Whatever you do anywhere seems to affect
matters everywhere else, in a manner that is difficult to
This page and its attachments are organized around a talk first given
on May 2, 1997. I'll describe the multivariate spline problem,
the four color map problem, the connections, and a proof of a
simple spline problem by four color map techniques. The hope is
that ultimately the spline problem will yield to the four color
If you have any comments or questions
I'd very much like to hear from you.
If you like more information, follow the links below:
Go to Peter Alfeld's Home Page.