Chaikin subdivision 2026-10-14
Chaikin subdivision generates a rounded subdivision curve by repeatedly cutting the corners off a control polygon. Each edge contributes two new control points, one a quarter of the way along the edge and the other three quarters of the way along it. Connecting these new control points in edge order replaces the old corners by shorter line segments. This makes Chaikin subdivision a useful way to draw a smooth outline from a small, editable set of control points, without evaluating B-spline basis functions at each drawing step. Joy presents both the corner-cutting rule and its closed version.[ref]
For a closed control polygon with control points , set and interpret indices cyclically. One refinement gives
and the new control polygon is the ordered sequence
Close it by joining back to . Use the old control points for every average in the same refinement; updating them in place would define a different algorithm. One refinement produces stored control points, and refinements produce , counting entries even if some coordinates coincide. Open control polygons need an explicit endpoint convention: applying only the interior edge rule discards the original endpoints, whereas retaining endpoints changes the boundary rule. The closed analysis below uses cyclic indices throughout.
For a worked example, start with the rectangular control polygon
The first edge gives and . Applying Chaikin subdivision to all four edges, including the closing edge, gives exactly eight control points in this order:
Thus the rectangle becomes an octagonal control polygon. Two refinements have control points, and five have . The illustration shows finite control polygons at stages ; the last is already visually rounded but still consists of line segments.
Figure 1.
Chaikin corner cutting on a rectangle at iterations zero, one, two and five
. The dashed rectangle is the original control polygon and its convex hull. Blue line segments and dots show the current control polygon and control points; no panel claims to be the exact limiting curve. Details.
The convex hull property follows directly from the weights. Each new control point is a convex combination of the endpoints of one old edge, because the weights are nonnegative and sum to one. Consequently, if is the convex hull of the stage- control points, then . Every later line segment, and every limit point, stays in the original convex hull. This gives a useful geometric enclosure. It also explains why Chaikin subdivision is approximating rather than an interpolation rule: the rectangle's four original corners are outside the first octagon's convex hull, so the limiting curve cannot pass through them. A refinement control polygon generally lies off the limiting curve as well.
For the cyclic uniform rule, the closed limit is the periodic quadratic uniform B-spline curve determined by the original control points. Uniform refers to equal spacing in the spline knot sequence, not equal physical lengths of edges of the control polygon. An infinite uniform control sequence has the corresponding local description; arbitrary open endpoint conventions need separate treatment. Joy derives the quarter-point refinement by splitting quadratic uniform B-spline spans.[ref]
Here is an explicit description of that closed limit, with cyclic indices and a unit parameter span for each original control point:
Each coordinate is a quadratic polynomial, and the three coefficients form a nonnegative partition of unity. The span runs from to . Differentiating gives and , so adjacent spans have matching values and matching first derivatives. Their second derivatives generally differ. Thus the parameterized curve is , generally not ; degenerate control points can still make its tangent vector vanish. For the rectangle, the span around is
which rounds the original corner between edge midpoints and . For equally spaced abscissae, the centered Chaikin basis function gives the scalar graph version of this quadratic B-spline representation and has support of width three original grid intervals.
Another useful property is affine equivariance of a geometric basis: refining and applying an affine map commute. For ,
and the same calculation holds for . The sum-to-one weights account for the translation. Therefore at every refinement, and also for the limit. A designer can apply a shear mapping, translation, or other affine map to the original control polygon and obtain exactly the transformed outline.
For example, compose the shear mapping with the translation to obtain . The rectangle's control points become . On its right edge, cutting first gives and then . Transforming first and cutting instead gives , the same control point.
Figure 2.
Shearing and translating a control polygon commutes with one Chaikin refinement
. Left: the rectangle and its first refinement. Right: the transformed control polygon, with blue dots from cutting after the affine map and orange rings from applying the affine map after cutting. All eight pairs coincide. Details.
Historically, George M. Chaikin published “An algorithm for high-speed curve generation” in Computer Graphics and Image Processing 3(4), December 1974, pages 346–349. Its emphasis was practical curve generation through a recursive algorithm using simple arithmetic, with applications including machine control and three-dimensional curves. The lasting appeal of Chaikin subdivision is how an elementary local average creates an entire smooth B-spline curve.[ref]
For a nonnegative partition-normalized B-spline basis, the synthesis linear map has operator norm one. Its condition number is consequently , with the supremum norm on the spline space and the maximum norm on its coefficients. The uniform-norm stability of a B-spline basis bounds this number independently of the spline knot sequence when the order is fixed. This is different from the condition number of a particular sampled B-spline collocation matrix.
Knot insertion 2026-10-14
Knot insertion refines the spline knot sequence and changes the control points without changing the represented B-spline. Repeated insertion exposes local Bézier curves and provides subdivision-based evaluation.
// Target: analysis.bigb
For an open clamped spline knot sequence and degree , the Greville abscissae reproduce the parameter. The B-spline differentiation formula gives derivative coefficients . Their lower-degree partition of unity makes the derivative of the weighted sum equal to one. The left endpoint value is the left parameter endpoint, fixing the integration constant to zero. This proves linear precision even with unequal knot intervals.
Linear spline 2026-10-14
A linear spline is a continuous piecewise linear function on a specified spline knot sequence. For uniform integer spline knots, the hat basis in the displayed representation interpolates the data . The derivative is constant on each open span and can jump at a knot. Coinciding neighboring slopes remove a particular jump, but generic data give only regularity.
A non-uniform rational B-spline surface is
Here the and are B-spline basis functions for possibly nonuniform spline knot sequences, and the are weights. Positive weights make each evaluated point a convex combination of the active control points, supplying bounding volumes for geometric searches. The denominator must remain nonzero for the parametrization to be defined.
The Korovkin theorem says that a sequence of positive linear operators on continuous functions on converges uniformly to the identity on every continuous function if it does so on , and . Necessity is immediate; the quadratic barrier argument establishing sufficiency is given in Solution 6.
There is an endpoint misprint in the original PDF: the repeated knots at the right end must equal , not . Otherwise the advertised nondecreasing spline knot sequence on does not exist. Use the corrected clamped spline knot sequences, with fixed order and maximum gap . Let denote the number of B-splines for the th sequence. Nonnegativity and partition of unity show that the Schoenberg spline operator is positive and .
The monomial B-spline coefficients reproduce the first two nonconstant test polynomials. Put
The pair sum uses , as in the PDF; the converted TeX incorrectly includes . Every sampling point and every knot entering these coefficients lie in , whose length is at most . Thus . Also all these numbers belong to , so
The positive B-spline weights give
Together with , the three limits prove
Under the usual interior knot multiplicities at most , the splines are continuous and the quoted form of the Korovkin theorem applies directly. If full interior multiplicity is allowed, the output can be discontinuous. The same positive-operator quadratic barrier proof still works with bounded output functions and the supremum norm, and proves exactly the stated uniform error limit without asserting continuity of each output. Indeed the stronger local-support error bound for a Schoenberg spline operator, , follows by comparing with each active sample value. The restriction is needed for the displayed quadratic reproduction argument, not for this direct support estimate.
Fix a clamped nondecreasing spline knot sequence on , with and . For continuous splines assume interior multiplicities at most , and assume . An order- spline has degree at most on each nonempty knot interval; at a knot of multiplicity it has continuous derivatives. Its dimension is , and a normalized B-spline basis has local support, nonnegative values and sum one on .
These properties are visible in the Cox-de Boor recurrence. Starting with interval indicators at order one, set
with a term of zero denominator defined to be zero. On each contributing support the weights are nonnegative, and summing the recurrence makes the coefficients of each lower-order B-spline add to one. This gives partition of unity and , with endpoint values defined by limits.
At distinct ordered sites , interpolation is the linear system
It has a unique solution for every data vector exactly when the B-spline collocation matrix is invertible. The Schoenberg–Whitney theorem characterizes this by for every ; away from clamped endpoints this is . At the clamped endpoints the first and last B-splines have value one, so the endpoint version uses this positive-value formulation rather than the strict inequalities. Both ordering and the support conditions matter. A spline space with interior knots is generally not a Chebyshev system on the entire interval: a locally supported B-spline vanishes on an interval. Thus arbitrary distinct nodes need not permit interpolation. Merely specifying all data sites as knots also need not fix the remaining freedom; for example, cubic interpolation with simple interior knots at data sites has dimension , and two extra boundary conditions are needed to interpolate values uniquely.
The positivity governing this existence theorem is total nonnegativity of B-spline collocation matrices: every square minor with increasing row and column indices is nonnegative. In spline terminology this is often called total positivity, but it permits zero minors caused by disjoint supports. It is not the stronger assertion that every minor is strictly positive. A useful proof uses knot insertion. Each refinement step changes coefficients by
with the unchanged endpoint pieces. The refinement matrix is nonnegative bidiagonal, and its minors are nonnegative: any nonzero determinant has its allowed diagonal matching and is a product of nonnegative entries. Products preserve this property by the Cauchy–Binet formula. Insert each sampling site to full multiplicity, so evaluation at that site becomes selection of an ordered refined coefficient. The collocation matrix is then an ordered row submatrix of the refinement product, proving total nonnegativity. The strict support criterion is the strict part of this argument: an ordered path through the consecutive support intervals exists exactly when every diagonal B-spline value is positive, giving the Schoenberg–Whitney theorem determinant criterion.
If is invertible, its determinant is positive and the adjugate identity yields
This checkerboard inverse of a totally nonnegative matrix is the central stability fact. With alternating data , the absolute row sums satisfy
For general data, the cardinal splines are . The spline interpolation operator and its exact Lebesgue constant of interpolation are
The equality for the operator norm follows by extending the signs at distinct sites to a continuous unit-norm data function, as in Solution 2. That solution also shows the last inequality can be very strict. Stability concerns the range function as well as its coefficients.
An optimal interpolation set must be specified relative to an objective. For the normalized B-spline coefficients, every admissible sampling set satisfies
since and sampling cannot increase the supremum norm. If a unit-norm spline has ordered alternating extrema at admissible sites, the checkerboard identity gives
Taking the largest row shows , so equality holds. This proves the optimal spline coefficient interpolation sites property and the Chebyshev spline coefficient and dual norm equality. In particular, for the cubic space of Solution 1 the alternating extrema satisfy the support conditions. Its coefficients have maximum magnitude , so these sites are optimal for coefficient recovery and
The argument proves optimality whenever this admissible equioscillating spline is available; it does not identify extrema of an arbitrary spline as optimal sites, or transfer coefficient optimality automatically to the Lebesgue constant of interpolation.
For the intrinsic interpolation objective, minimize itself. There is a minimizer for a fixed finite-dimensional continuous spline space. Indeed the sites lie in a compact ordered simplex. On admissible sets, inverse entries and hence vary continuously. As a collocation matrix tends to a singular one, its inverse norm diverges. The uniform-norm stability of a B-spline basis gives the complementary bound
choose sample signs attaining a largest inverse row, extend them to a continuous unit-norm function, and use . Thus a minimizing sequence with bounded Lebesgue constants of interpolation cannot approach a singular site set. A convergent subsequence has an admissible limit attaining the minimum.
Fekete interpolation sites for a continuous function space offer another useful, constructive criterion: maximize the absolute evaluation determinant. A nonzero maximum exists by compactness and linear independence. Replacing one row by evaluation at multiplies the determinant by the corresponding cardinal function, so maximality gives , and therefore . These sites are determinant-optimal, with a proven interpolation bound; one should not claim without further argument that they minimize . Greville abscissae provide inexpensive admissible sites for the usual continuous clamped spline spaces of order at least two. Admissibility alone does not give the best stability bound.
Finally, the coefficient condition number of a normalized B-spline basis is bounded by a constant depending only on order. To see the mechanism, for each coefficient choose a longest nonempty knot cell in that B-spline's support. If its length is and the support width is , then . On that cell the spline is a degree-at-most- polynomial; repeated Markov polynomial inequalities bound its th derivative by . In the De Boor–Fix spline coefficient functional, the accompanying derivative of the knot polynomial is bounded by . Each term is consequently at most , yielding independently of the number and spacing of knots. This is basis stability; it does not bound at arbitrarily poor sampling sites.
For approximation, reproduction gives the Lebesgue inequality for approximation projectors
As the maximum knot gap tends to zero with fixed order, spline quasi-interpolation gives an approximant with error at most , so the infimum tends to zero. A sequence of uniformly bounded interpolation linear operators therefore converges to every continuous target. Local support and a stable choice of sites make spline interpolation effective; mesh refinement without control of the interpolation operator norm is not by itself a convergence proof.
Assume the spline knot sequence is ordered and its relevant support spans satisfy . For distinct knots, the divided difference is a finite linear combination of evaluations, so it commutes with integration. With ,
Taking the order- divided difference in gives
Indeed, the order- divided difference of a degree- polynomial is its leading coefficient, here . This proves the unit-integral normalization of a B-spline. Admissible repeated knots follow by coalescing knots, with the usual one-sided endpoint conventions.
Use the quartic treble-knot representation of a quadratic B-spline. Specify the indexing as well as the controls: for the interior of the long curve, take the quartic spline knot sequence
With the standard B-spline convention that control multiplies supported on , the answer is
In other words, keep the three interior quartic Bézier curve controls for each span in that order. The offset matters for the stated knot indexing; shifting all indices together gives an equivalent convention.
To prove the representation, insert each integer interior knot once, changing multiplicity three to four. A degree-four knot of multiplicity four separates Bézier curve spans while leaving their shared endpoint common. The three interior controls remain, and knot insertion constructs the shared endpoint from its neighboring controls with weights , since adjacent knot intervals have equal length. In fact,
The right endpoint is obtained in the same way. Hence every extracted quartic span has exactly the five controls proved in part (b). Knot insertion leaves the curve unchanged, so the assembled quartic B-spline is identical to the original quadratic one on every span.
There is also a derivative check at each join:
This is why treble knots are appropriate: degree four with interior knot multiplicity three permits continuity, exactly the generic continuity of the uniform quadratic B-spline. For a finite clamped curve, include its endpoint controls and endpoint knot multiplicities using the same degree elevation of Bernstein coefficients and knot insertion; the displayed formulas describe the long interior requested here, without imposing an unstated end condition.
Use the usual strictly increasing spline knot sequence, and initially assume . The explicit formula for the order- divided difference gives
Each summand is a truncated power function in , with its junction at . It is a piecewise polynomial function of degree at most and has continuous derivatives. Finite summation preserves these properties.
For all summands vanish. For , all spline knot data come from the polynomial . An order- divided difference annihilates a polynomial of smaller degree, so there too. Thus the support is contained in .
On the last open spline knot interval only the term survives; it is a nonzero multiple of . On the first open spline knot interval, compare the truncated spline knot data with the untruncated polynomial data: only the value differs. Since the untruncated divided difference is zero, the result is a nonzero multiple of . Consequently both outer pieces are nonzero, giving exact closed support. The Cox-de Boor recurrence used below also proves positivity throughout the open support. Therefore
This is simple-knot B-spline regularity. For the B-splines are interval indicators; they are piecewise constant and need not be continuous. The notation should then be read as no continuity requirement, not as a classical negative-order differentiability space.
The divided difference is a finite linear combination of spline knot values, so it commutes with the finite integral. For every spline knot in the defining interval,
It follows that
because the order- divided difference of a monic degree- polynomial is its leading coefficient. This proves the unit-integral normalization of a B-spline.
For the partition of unity, let denote the partition-normalized order- B-spline. The Cox-de Boor recurrence is
It follows by substituting the explicit divided difference formula into both sides and collecting each truncated power function. The starting case is , with endpoint conventions irrelevant when . The two weights are nonnegative wherever their respective lower-order B-splines are nonzero. Induction therefore gives and strict positivity in its open support.
Extend the finite spline knot sequence strictly in both directions, with no finite accumulation. At each point only finitely many B-splines are nonzero. For the full extended family the sum is one for order one. Summing the Cox-de Boor recurrence, the combined coefficient of is
Induction gives a full partition of unity at every order. On , all extended order- functions with index or vanish by their supports. Hence
The same argument gives the useful global subpartition of unity for B-splines, , including outside the basic spline knot interval.
For on an equidistant spline knot sequence, is the triangular hat with value one at and support . Its slopes on the two pieces are and , and . Direct integration gives
Nonadjacent hats have disjoint interiors of their supports, so their inner product vanishes. Dividing by therefore gives
This linear-spline mixed Gram matrix is tridiagonal. Every diagonal entry is , including the first and last: the distinct-knot hats have their full supports inside . End rows simply lack one off-diagonal neighbor; there are no repeated endpoint spline knots here.
A strict diagonal dominance argument proves the estimate even on a nonuniform strictly increasing spline knot sequence. Put . Then has a rising piece of length and a falling piece of length , while . The same integrations as in part (b) give the linear-spline mixed Gram matrix
Only entries with indices in are present. Thus in every row.
For , choose an index with . The reverse triangle inequality then yields
Hence . Applying this to every proves
This is the inverse infinity-norm bound from diagonal dominance; no total positivity theorem is needed. The proof also gives invertibility directly by taking .
Write , and let . We use the standard interpolation convention of distinct ordered sites . Together with , the Schoenberg–Whitney theorem makes the B-spline collocation matrix invertible. Equivalently, its invertibility is implicit in the existence of the interpolation operator for every data vector.
If distinctness is not understood, the printed positivity condition alone is insufficient. For the order-two basis on spline knots , take . Both diagonal B-spline values are , but the two rows of coincide. Arbitrary data cannot then be interpolated uniquely. The norm statement below concerns the intended well-defined interpolation operator.
Spline interpolation determines the coefficient vector by , and hence
Nonnegativity and the subpartition of unity for B-splines give
For completeness, extend the finite spline knot sequence beyond both ends. For the full sequence the order-one interval indicators sum to one. Summing the Cox-de Boor recurrence and shifting the index in its second term combines the two coefficients of each lower-order B-spline to one, so induction gives partition of unity at every order. Our finite collection is a subset of that nonnegative collection, and thus has sum at most one. Repeated spline knots are handled by the standard zero-term convention or a knot limit. This argument controls the entire interval, not only the basic knot interval.
Since , the operator norm upper bound is
Here the matrix operator norm is the maximum absolute row sum. For the lower bound, choose a row of with maximum absolute row sum and a data vector whose components are the signs of that row's entries. Then and
A continuous piecewise-linear function taking these values at the distinct ordered sites, and constant outside their range, has supremum norm one. Apply the given uniform-norm stability of a B-spline basis to its coefficient vector:
Therefore
The construction of the bounded continuous data extension is what permits the matrix norm to give a lower bound for a function-space operator norm.
For a uniform quadratic B-spline with interior control points , label its th span . A quartic B-spline with interior spline knot sequence represents the identical curve when
To verify this, raise each quadratic Bézier curve span twice by degree elevation of Bernstein coefficients. The three interior quartic controls are the displayed points. One additional knot insertion at each interior knot supplies the shared endpoint as the mean of its two neighboring controls, recovering all five quartic Bézier curve controls. Thus the knot multiplicity is three, giving joins rather than imposing unwanted extra smoothness.