NationMaster - Encyclopedia: Spline (mathematics)

In the mathematical subfield of numerical analysis, a spline is a special function defined piecewise by polynomials. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree polynomials, while avoiding Runge's phenomenon for higher degrees. Diagram of a bézier curve. ... Diagram of a bézier curve. ... In the mathematical subfield of numerical analysis a BÃ©zier curve is a parametric curve important in computer graphics. ... Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ... Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... In mathematics, a function f(x) of a real number variable x is defined piecewise, if f(x) is given by different expressions on various intervals. ... In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ... In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ... In the mathematical subfield of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. ... In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ... The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. ...

In the computer science subfields of computer-aided design and computer graphics, the term spline more frequently refers to a piecewise parametric polynomial curve. Splines are a popular representation of curves in these subfields because of the simplicity of their construction, their ease and accuracy of evaluation, and their capacity to approximate complex shapes through curve fitting and interactive curve design. Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... ECAD redirects here. ... Computer graphics (CG) is the field of visual computing, where one utilizes computers both to generate visual images synthetically and to integrate or alter visual and spatial information sampled from the real world. ... In mathematics, the differential geometry of curves provides definitions and methods to analyze smooth curves in Riemannian manifolds and Pseudo-Riemannian manifolds (and in particular in Euclidean space) using differential and integral calculus. ... Curve fitting is finding a curve which matches a series of data points and possibly other constraints. ...

The term spline comes from the flexible spline devices used by shipbuilders and draftsmen to draw smooth shapes. A spline consists of a long strip of wood (a lath, not to be confused with lathe) fixed in position at a number of points. ... This is about drafting, the art and science of technical drawing. ...

1 Introduction
2 Definition
3 Examples
4 Notes
5 Representations and names
6 History
7 References
8 External links

Introduction

The term "spline" is used to refer to a wide class of functions that are used in applications requiring data interpolation and/or smoothing. Splines may be used for interpolation and/or smoothing of either one-dimensional or multi-dimensional data. Spline functions for interpolation are normally determined as the minimizers of suitable measures of roughness (for example integral squared curvature) subject to the interpolation constraints. Smoothing splines may be viewed as generalizations of interpolation splines where the functions are determined to minimize a weighted combination of the average squared approximation error over observed data and the roughness measure. For a number of meaningful definitions of the roughness measure, the spline functions are found to be finite dimensional in nature, which is the primary reason for their utility in computations and representation. For the rest of this section, we focus entirely on one-dimensional, polynomial splines and use the term "spline" in this restricted sense.

Definition

A (univariate, polynomial) spline is a piecewise polynomial function. In its most general form a polynomial spline $S: [a,b]to mathbb{R}$ consists of polynomial pieces $P_i: [t_i, t_{i+1}]to mathbb{R}$ , where In mathematics, a function f(x) of a real number variable x is defined piecewise, if f(x) is given by different expressions on various intervals. ...

$a=t_0 < t_1 < cdots < t_{k-2} < t_{k-1} = b$ .

That is,

$S(t) = P_0 (t) mbox{ , } t_0 le t < t_1,$

$S(t) = P_1 (t) mbox{ , } t_1 le t < t_2,$

$cdots$

$S(t) = P_{k-2} (t) mbox{ , } t_{k-2} le t le t_{k-1}.$

The given k points t_i are called knots. The vector ${bold t}=(t_0, dots, t_{k-1})$ is called a knot vector for the spline. If the knots are equidistantly distributed in the interval [a,b] we say the spline is uniform, otherwise we say it is non-uniform.

If the polynomial pieces on the subintervals

$[t_i,t_{i+1}] mbox{ , } i = 0,ldots k-2$

all have degree at most n, then the spline is said to be of degree $leq n$ (or of order n+1).

If $Sin C^{r_i}$ in a neighborhood of $t i$ , then the spline is said to be of smoothness (at least) $C^{r_i}$ at $t i$ . That is, the two pieces $P i - 1$ and $P i$ share common derivative values from the derivative of order 0 (the function value) up through the derivative of order r_i. Or stated differently, the two adjacent polynomial pieces connect with loss of smoothness of (at most) j_i, defined by $r i = n - j i$ . (Expressing the connectivity as a "loss of smoothness" is reasonable, since if S were a simple polynomial throughout a neighborhood of t_i, it would have smoothness Cⁿ at t_i, and you would expect to lose smoothness in order to break a polynomial apart into pieces.) A vector ${bold r}=(r_1, dots, r_{k-2})$ such that the spline has smoothness $C^{r_i}$ at $t i$ for $0 < i < k - 1$ is called a smoothness vector for the spline.

Given a knot vector ${bold t}$ , a degree n, and a smoothness vector ${bold r}$ for ${bold t}$ , one can consider the set of all splines of degree $leq n$ having knot vector ${bold t}$ and smoothness vector ${bold r}$ . Equipped with the operation of adding two functions (pointwise addition) and taking real multiples of functions, this set becomes a real vector space. This spline space is commonly denoted by $S^{bold r}_n({bold t})$ .

In the mathematical study of polynomial splines the question of what happens when two knots, say t_i and t_i+1, are moved together has an easy answer. The polynomial piece P_i(t) disappears, and the pieces P_i−1(t) and P_i+1(t) join with the sum of the continuity losses for t_i and t_i+1. That is,

$S(t) in C^{n-j_i-j_{i+1}} [t_i = t_{i+1}]$

This leads to a more general understanding of a knot vector. The continuity loss at any point can be considered to be the result of multiple knots located at that point, and a spline type can be completely characterized by its degree n and its extended knot vector

$a=t_0 < t_1 = cdots = t_1 < cdots < t_{k-2} = cdots = t_{k-2} < t_{k-1} = b$

where $t i$ is repeated $j i$ times for $i = 1, dots , k-2$ .

A parametric curve on the interval [a,b] In mathematics, the differential geometry of curves provides definitions and methods to analyze smooth curves in Riemannian manifolds and Pseudo-Riemannian manifolds (and in particular in Euclidean space) using differential and integral calculus. ...

$G(t) = < X(t), Y(t) > mbox{ , } t in [ a , b ]$

is a spline curve if both X and Y are splines of the same degree with the same extended knot vectors on that interval.

Examples

Suppose the interval [a,b] is [0,3] and the subintervals are [0,1), [1,2), and [2,3]. Suppose the polynomial pieces are to be of degree 2, and the pieces on [0,1) and [1,2) must join in value and first derivative (at t=1) while the pieces on [1,2) and [2,3] join simply in value (at t=2). This would define a type of spline $S (t)$ for which

$S(t) = P_0 (t) = -1+4t-t^2 mbox{ , } 0 le t < 1$

$S(t) = P_1 (t) = 2t mbox{ , } 1 le t < 2$

$S(t) = P_2 (t) = 2-t+t^2 mbox{ , } 2 le t le 3$

would be a member of that type, and also

$S(t) = P_0 (t) = -2-2t^2 mbox{ , } 0 le t < 1$

$S(t) = P_1 (t) = 1-6t+t^2 mbox{ , } 1 le t < 2$

$S(t) = P_2 (t) = -1+t-2t^2 mbox{ , } 2 le t le 3$

would be a member of that type. (Note: the polynomial piece $2 t$ is quadratic, since it can be written $2 t + 0 t 2$ . Any polynomial of one degree is trivially a polynomial of higher degree simply by this trick of adding appropriate powers with zero coefficients.) The extended knot vector for this type of spline would be $0,1,2,2,3$ .

The simplest spline has degree 0. It is also called a step function. The next most simple spline has degree 1. It is also called a linear spline. The corresponding parametric curve having linear spline components X(t) and Y(t) just a polygon. A function on the reals is a step function if it can be written as a finite linear combination of semi-open intervals. ... Look up Polygon in Wiktionary, the free dictionary. ...

A common spline is the natural cubic spline of degree 3 with continuity $C 2$ . The word "natural" means that the second derivatives of the spline polynomials are set equal to zero at the endpoints of the interval of interpolation

$S''(a) , = S''(b) = 0$ .

This forces the spline to be a straight line outside of the interval, while not disrupting its smoothness.

Notes

It might be asked what meaning more than $n$ multiple knots in a knot vector have, since this would lead to continuities like

$S(t) in C^{-m} mbox{ , } m > 0$

at the location of this high multiplicity. By convention, any such situation indicates a simple discontinuity between the two adjacent polynomial pieces. This means that if a knot $t i$ appears more than $n + 1$ times in an extended knot vector, all instances of it in excess of the $n + 1 s t$ can be removed without changing the character of the spline, since all multiplicities $n + 1$ , $n + 2$ , $n + 3$ , etc. have the same meaning. It is commonly assumed that any knot vector defining any type of spline has been culled in this fashion.

The classical spline type of degree n used in numerical analysis has continuity

$S(t) in mathrm{C}^{n-1} [a,b]$ ,

which means that every two adjacent polynomial pieces meet in their value and first n-1 derivatives at each knot. The mathematical spline that most closely models the spline (device) is a cubic (n=3), twice continuously differentiable (C²), natural spline, which is a spline of this classical type with additional conditions imposed at endpoints a and b. A spline consists of a long strip of wood (a lath, not to be confused with lathe) fixed in position at a number of points. ...

Another type of spline that is much used in graphics, for example in drawing programs such as Adobe Illustrator from Adobe Systems, has pieces that are cubic but has continuity only at most Adobe Illustrator is a vector-based drawing program developed and marketed by Adobe Systems. ... Adobe Systems (NASDAQ: ADBE) (LSE: ABS) is an American computer software company headquartered in San Jose, California that was founded in December 1982 by John Warnock and Charles Geschke. ...

$S(t) in mathrm{C}^{1} [a,b]$ .

This spline type is also used in PostScript as well as in the definition of some computer typographic fonts. PostScript (PS) is a page description language and programming language used primarily in the electronic and desktop publishing areas. ...

Many computer-aided design systems that are designed for high-end graphics and animation use extended knot vectors, for example Maya from Alias. Computer-aided design systems often use an extended concept of a spline known as a Nonuniform rational B-spline (NURBS). Maya is a high-end 3D computer graphics software package by Alias but now owned by Autodesk Media & Entertainment used in the film and TV industry, as well as for computer and video games. ... Alias Systems Corporation (formerly Alias|Wavefront), headquartered in Toronto, Ontario, Canada, is a software company that produces high-end 3D graphics software. ... NURBS, short for non-uniform, rational B-spline, is a mathematical model commonly used in computer graphics for generating and representing curves and surfaces. ...

If sampled data from a function or a physical object is available, spline interpolation is an approach to creating a spline that approximates that data. In the mathematical subfield of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. ...

Representations and names

For a given interval $[a, b]$ and a given extended knot vector on that interval, the splines of degree n form a vector space. Briefly this means that adding any two splines of a given type produces spline of that given type, and multiplying a spline of a given type by any constant produces a spline of that given type. The dimension of the space containing all splines of a certain type can be counted from the extended knot vector: Vector spaces (or linear spaces) are spaces whose elements, known as vectors, can be scaled and added; all linear combinations can be formed. ... In mathematics, the dimension of a vector space V is the cardinality (i. ...

$a = t_0 < underbrace{t_1 = cdots = t_1}_{j_1} < cdots < underbrace{t_{k-2} =cdots =t_{k-2}}_{j_{k-2}} < t_{k-1} = b$

$j_i le n+1 ~,~~ i=1,ldots,k-2$

The dimension is equal to the sum of the degree plus the multiplicities

$d = n + sum_{i=1}^{k-2} j_i$

If a type of spline has additional linear conditions imposed upon it, then the resulting spline will lie in a subspace. The space of all natural cubic splines, for instance, is a subspace of the space of all cubic $C 2$ splines.

The literature of splines is replete with names for special types of splines. These names have been associated with:

The choices made for representing the spline, for example:
- using basis B-splines as basis functions for the entire spline (giving us the name B-splines)
- using Bernstein polynomials as employed by Pierre Bézier to represent each polynomial piece (giving us the name Bézier splines)
The choices made in forming the extended knot vector, for example:
- using single knots for $C n - 1$ continuity and spacing these knots evenly on [a,b] (giving us uniform splines)
- using knots with no restriction on spacing (giving us nonuniform splines)
Any special conditions imposed on the spline, for example:
- enforcing zero second derivatives at a and b (giving us natural splines)
- requiring that given data values be on the spline (giving us interpolating splines)

Often a special name was chosen for a type of spline satisfying two or more of the main items above. For example, the Hermite spline is a spline that is expressed using Hermite polynomials to represent each of the individual polynomial pieces. These are most often used with $n = 3$ ; that is, as Cubic Hermite splines. In this degree they may additionally be chosen to be only tangent-continuous ( $C 1$ ); which implies that all interior knots are double. Several methods have been invented to fit such splines to given data points; that is, to make them into interpolating splines, and to do so by estimating plausible tangent values where each two polynomial pieces meet (giving us Cardinal splines, Catmull-Rom splines, and Kochanek-Bartels splines, depending on the method used). In the mathematical subfield of numerical analysis a B_spline is a special spline curve. ... In linear algebra, a basis is a minimum set of vectors that, when combined, can address every vector in a given space. ... In the mathematical subfield of numerical analysis a B-spline is a spline function which has minimal support with respect to a given degree, smoothness, and domain partition. ... In the mathematical subfield of numerical analysis, a Bernstein polynomial, named after Sergei Natanovich Bernstein, is a polynomial in the Bernstein form, that is a linear combination of Bernstein basis polynomials. ... In the mathematical subfield of numerical analysis and in computer graphics a BÃ©zier spline is a spline curve where each polynomial of the spline is in BÃ©zier form. ... In the mathematical subfield of numerical analysis a Hermite spline is a spline curve where each polynomial of the spline is in Hermite form. ... In the mathematical subfield of numerical analysis a cubic Hermite spline, named in honor of Charles Hermite (Hermite is pronounced air MIT), is a third-degree spline with each polynomial of the spline in Hermite form. ... A cardinal spline is a cubic Hermite spline whose tangents are defined by the points and a tension parameter. ... In mathematics, a Catmull-Rom spline is a cardinal spline with a tension of 0. ... In mathematics, a Kochanek-Bartels spline or Kochanek-Bartels curve is a cubic Hermite spline with tension, bias, and continuity parameters defined to change the behavior of the tangents. ...

For each of the representations, some means of evaluation must be found so that values of the spline can be produced on demand. For those representations that express each individual polynomial piece $P i (t)$ in terms of some basis for the degree n polynomials, this is conceptually straightforward:

For a given value of the argument t, find the interval in which it lies $t in [t_i,t_{i+1})$
Look up the polynomial basis chosen for that interval $P_0, ldots, P_{k-2}$
Find the value of each basis polynomial at $, t$ : $P_0(t), ldots, P_{k-2}(t)$
Look up the coefficients of the linear combination of those basis polynomials that give the spline on that interval $c_0, ldots, c_{k-2}$
Add up that linear combination of basis polynomial values to get the value of the spline at $, t$ : $sum_{j=0}^{k-2} c_j P_j(t)$

However, the evaluation and summation steps are often combined in clever ways. For example, Bernstein polynomials are a basis for polynomials that can be evaluated in linear combinations efficiently using special recurrence relations. This is the essence of De Casteljau's algorithm, which features in Bézier curves and Bézier splines. In the mathematical subfield of numerical analysis the de Casteljaus algorithm, named after its inventor Paul de Casteljau, is a recursive method to evaluate polynomials in Bernstein form or BÃ©zier curves. ... In the mathematical subfield of numerical analysis a BÃ©zier curve is a parametric curve important in computer graphics. ... In the mathematical subfield of numerical analysis and in computer graphics a BÃ©zier spline is a spline curve where each polynomial of the spline is in BÃ©zier form. ...

For a representation that defines a spline as a linear combination of basis splines, however, something more sophisticated is needed. The de Boor algorithm is an efficient method for evaluating B-splines. In the mathematical subfield of numerical analysis the De Boor algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. ... In the mathematical subfield of numerical analysis a B-spline is a spline function which has minimal support with respect to a given degree, smoothness, and domain partition. ...

History

Before computers were used, numerical calculations were done by hand. Although piecewise-defined functions like the signum function or step function were used, polynomials were generally preferred because they were easier to work with. Through the advent of computers splines have gained importance. They were first used as a replacement for polynomials in interpolation, then as a tool to construct smooth and flexible shapes in computer graphics. Signum function In mathematics and especially in computer science, the sign function is a logical function which extracts the sign of a real number. ... A function on the reals is a step function if it can be written as a finite linear combination of semi-open intervals. ...

It is commonly accepted that the first mathematical reference to splines is the 1946 paper by Schoenberg, which is probably the first place that the word "spline" is used in connection with smooth, piecewise polynomial approximation. However, the ideas have their roots in the aircraft and ship-building industries. In the foreword to (Bartels et al., 1987), Robin Forrest describes "lofting," a technique used in the British aircraft industry during World War II to construct templates for airplanes by passing thin wooden strips (called "splines") through points laid out on the floor of a large design loft, a technique borrowed from ship-hull design. For years the practice of ship design had employed models to design in the small. The successful design was then plotted on graph paper and the key points of the plot were re-plotted on larger graph paper to full size. The thin wooden strips provided an interpolation of the key points into smooth curves. The strips would be held in place at discrete points (called "ducks" by Forrest; Schoenberg used "dogs" or "rats") and between these points would assume shapes of minimum strain energy. According to Forrest, one possible impetus for a mathematical model for this process was the potential loss of the critical design components for an entire aircraft should the loft be hit by an enemy bomb. This gave rise to "conic lofting," which used conic sections to model the position of the curve between the ducks. Conic lofting was replaced by what we would call splines in the early 1960's based on work by J. C. Ferguson at Boeing and (somewhat later) by M.A. Sabin at British Aircraft Corporation. Isaac Jacob Schoenberg (April 21, 1903 - February 21, 1990) was a Romanian mathematician who was born in Galati, Romania. ... Combatants Allies: Poland, British Commonwealth, France/Free France, Soviet Union, United States, China, and others Axis Powers: Germany, Italy, Japan, and others Casualties Military dead: 17 million Civilian dead: 33 million Total dead: 50 million Military dead: 8 million Civilian dead: 4 million Total dead: 12 million World War II... A spline consists of a long strip of wood (a lath, not to be confused with lathe) fixed in position at a number of points. ... The Boeing Company (NYSE: BA, TYO: 7661 ) is the worldâ€™s largest aircraft manufacturer. ... The British Aircraft Corporation, or BAC, was a British aircraft manufacturer, formed from the forced merger of the Bristol Aeroplane Company, English Electric, Vickers-Armstrong and Hunting Aircraft Company in 1959. ...

The word "spline" was originally an East Anglian dialect word. East Anglia - the easternmost area of England - was probably home to the first-ever form of language which can be called English. ...

The use of splines for modeling automobile bodies seems to have several independent beginnings. Credit is claimed on behalf of de Casteljau at Citroën, Pierre Bézier at Renault, and Birkhoff, Garabedian, and de Boor at General Motors (see Birkhoff and de Boor, 1965), all for work occurring in the very early 1960s or late 1950s. At least one of de Casteljau's papers was published, but not widely, in 1959. De Boor's work at GM resulted in a number of papers being published in the early 60's, including some of the fundamental work on B-splines. Paul de Casteljau(1910 - 1999), an engineer a Citroen, developed an algorithm for computation of a BÃ©zier curve. ... CitroÃ«n is a French automobile manufacturer, started in 1919 by AndrÃ© CitroÃ«n, today part of PSA Peugeot CitroÃ«n. ... Pierre Ã‰tienne BÃ©zier (September 1, 1910, - November 25, 1999) was a French engineer and creator of the BÃ©zier curves and BÃ©zier surfaces that are now the basis of most computer-aided design and computer graphics systems. ... Renault S.A. is a French vehicle manufacturer producing small to upper-midsize cars, vans, buses and trucks. ... Garrett Birkhoff (January 19, 1911, Princeton, New Jersey, USA - November 22, 1996, Water Mill, New York, USA) was an American mathematician. ... Carl R. de Boor is professor emeritus at the University of Wisconsin. ... General Motors Corporation (NYSE: GM), also known as GM, is an American automobile maker with worldwide operations and brands including Buick, Cadillac, Chevrolet, GMC, Holden, Hummer, Opel, Pontiac, Saturn, Saab and Vauxhall. ... In the mathematical subfield of numerical analysis a B-spline is a spline function which has minimal support with respect to a given degree, smoothness, and domain partition. ...

Work was also being done at Pratt & Whitney Aircraft, where two of the authors of (Ahlberg et al., 1967) — the first book-length treatment of splines — were employed, and the David Taylor Model Basin, by Feodor Theilheimer. The work at GM is detailed nicely in (Birkhoff, 1990) and (Young, 1997). Davis (1997) summarizes some of this material.

References

Ahlberg, Nielson, and Walsh, The Theory of Splines and Their Applications, 1967.
Birkhoff, Fluid dynamics, reactor computations, and surface representation, in: Steve Nash (ed.), A History of Scientific Computation, 1990.
Bartels, Beatty, and Barsky, An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, 1987.
Birkhoff and de Boor, Piecewise polynomial interpolation and approximation, in: H. L. Garabedian (ed.), Proc. General Motors Symposium of 1964, pp. 164–190. Elsevier, New York and Amsterdam, 1965.
Davis, B-splines and Geometric design, SIAM News, vol. 29, no. 5, 1997.
Epperson, History of Splines, NA Digest, vol. 98, no. 26, 1998.
Schoenberg, Contributions to the problem of approximation of equidistant data by analytic functions, Quart. Appl. Math., vol. 4, pp. 45–99 and 112&nash;141, 1946.
Young, Garrett Birkhoff and applied mathematics, Notices of the AMS, vol. 44, no. 11, pp. 1446–1449, 1997.

External links

An Interactive Introduction to Splines
Learning by Simulations Interactive simulation of various cubic splines
C code to determine if a point lies in a polygon that includes spline curves

Categories: Splines

Results from FactBites:

Mathematics under the Microscope (1644 words)
	I was thinking, for some reason, about sums of two integer squares (an archetypal mathematical problem: representation of numbers by forms) and a remarkable fact that the if m and m are sums of two integer squares (let us call them bisquare numbers) then their product mn also has the same property.
	Based on your impressive record of mathematical achievements, you seem to be especially well-placed to help us find people with strong academic backgrounds whose areas of specialization might be particularly relevant to the work we do.
	A digitisation of the book is available from The Cornell Library Historical Mathematics Monographs website; I paged through the book: it is a quite serious text where geometry of 4-dimensional Euclidean space is developed by analogy with Euclidean stereometry, that is, 3-dimensional geometry.

Curve Segments (1015 words)
	Spline curves and polygons are collectively termed "faces", while grids and spline surfaces are termed "hulls".
	It is, however, useful to understand some of the concepts that arise from the mathematics of computer-generated curves because they affect your choice of curve type when you start creating in Houdini, and they influence the way you draw that curve.
	The more knots there are in one area, the smaller the spline segments and, therefore, you have a greater degree of control over the spline in that area.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Introduction GA_googleFillSlot("encyclopedia_square");