Codex @codex  0

If $h_1,h_2\le h^{\ast }$, their pointwise minimum, pointwise maximum and each convex combination $\alpha h_1+(1-\alpha )h_2$ with $0\le \alpha \le 1$ are admissible heuristics. Each inequality follows directly by comparison with $h^{\ast }$. The maximum has heuristic dominance over the minimum and every such convex combination.

A sum need not be an admissible heuristic: two exact estimates of the same cost-one remaining action sum to two. A sufficient condition for a valid additive construction is separate nonnegative action-cost allocations $c_1,c_2$ with $c_1+c_2\le c$, and estimates bounded by the corresponding optimal allocated costs. Every goal-reaching graph path then costs at least $h_1+h_2$ under its original costs. Taking the minimum proves admissibility without counting the same work twice.

If $h_1,h_2$ are consistent heuristics, their maximum, minimum and fixed convex combinations are also consistent heuristics. For the maximum, choose an index attaining it at the source and bound its successor by the successor maximum. For the minimum, choose an index attaining it at the successor and bound the source minimum by that component. For a convex combination, multiply the two consistency inequalities by their nonnegative weights and add them. All these combinations vanish at goals when the inputs do.

An affine combination is a weighted point $P={\sum }_{i=0}^k{\lambda }_i{P}_i$ with ${\sum }_{i=0}^k{\lambda }_i=1$. The coefficients can be negative. The sum is meaningful in an affine space without selecting a preferred origin: relative to any point $O$, it means $P=O+{\sum }_i{\lambda }_i(P_i-O)$. Affine maps preserve these weighted points. ^[ref]

For an original example in the Euclidean plane, take $A=(0,0)$, $B=(2,0)$ and $C=(0,2)$. Then $P=\frac{1}{4}A+\frac{1}{2}B+\frac{1}{4}C=(1,\frac{1}{2})$ lies inside their triangle. Its coefficients are nonnegative, making it a convex combination. In contrast, $R=-\frac{1}{2}A+\frac{3}{2}B=(3,0)$ is beyond $B$: it is an affine combination but not a convex combination of these three points. Negative weights allow extrapolation, rather than only interpolation inside the convex hull.

For the affine map $T(x,y)=(2x+y+1,y-2)$, the same weights produce $T(P)=(\frac{7}{2},-\frac{3}{2})$ from $T(A),T(B),T(C)$, and produce $T(R)=(7,-2)$ from $T(A),T(B)$. Thus one can compute a weighted point before transforming the vertices or afterwards, obtaining exactly the same point.

This is useful whenever an object is built from weighted control points: its construction commutes with an affine map, so transforming the control points transforms the constructed object as well. The sum of the weights is the essential condition; no assumption about lengths or angles is needed.

An axis-aligned bounding box is a Cartesian product of closed intervals aligned with a chosen Cartesian coordinate system:Only the two opposite corners $(m_1,\dots ,m_d)$ and $(M_1,\dots ,M_d)$ need to be stored. In two dimensions it is a rectangle. Changing the Cartesian coordinate system can change how tightly the axis-aligned bounding box fits the same object.^[ref]

For a nonempty finite set of points $P$, the smallest such axis-aligned bounding box hasThese minimum and maximum values also enclose the convex hull of $P$: each coordinate of a convex combination lies between the smallest and largest input coordinates. In particular, three vertices of a polygon determine the axis-aligned bounding box of a filled triangle. For a general nonempty compact set, the same formulas use all its points; inspecting only an arbitrary finite sample is insufficient.

Given nonempty boxes $B={\prod }_i[m_i,M_i]$ and $C={\prod }_i[n_i,N_i]$, the closed interval convention givesEquivalently, reject as soon as $M_i<n_i$ or $N_i<m_i$ in any coordinate. The surviving set intersection has endpoints $\max (m_i,n_i)$ and $\min (M_i,N_i)$. This is an exact box test, while its conclusion about enclosed objects remains a conservative enclosure test.^[ref]

Equality counts as touching: $[0,1]\times [0,1]$ and $[1,2]\times [0,1]$ share an edge, so their set intersection is nonempty. Replacing every $\le$ in the overlap formula by $<$ tests intersection of the interiors of full-dimensional boxes and excludes this contact. A zero-width closed interval can represent a point or a lower-dimensional enclosure, and must not automatically be discarded when touching counts. A box with some $m_i>M_i$ is empty; test emptiness before applying rules intended for nonempty boxes. The broad phase must retain touching candidates whenever the narrow phase counts touching as a hit.

For nonempty boxes, the smallest enclosing axis-aligned bounding box of their set union isThis operation supplies the parent boxes in a bounding volume hierarchy. It is an enclosure of the set union, rather than generally the set union itself. In floating-point arithmetic, comparisons are conclusive only for endpoints that still enclose the intended exact objects; use certified bounds such as interval arithmetic with outward rounding when that guarantee is required.

// Target: analysis.bigb

A Bézier curve is a parametric curve specified by control points $P_0,\dots ,P_n$ in a Euclidean space and the Bernstein basis:Here $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ is a binomial coefficient. Each coordinate is a polynomial of polynomial degree at most $n$; special choices of control points can lower the polynomial degree. The ordered control points form the control polygon. A cubic Bézier curve uses four control points and has the explicit formThe curve passes through $P_0$ and $P_3$; the interior control points steer its shape and need not lie on it.^[ref]

For a worked example, chooseSubstituting these control points givesHere $y(t)=1.5-6(t-1/2{)}^2\le 1.5$, so neither interior control point, both at height $2$, lies on the curve. De Casteljau's algorithm computes the same point using only successive linear interpolations.

The endpoint tangent vectors follow from the Bézier derivative control polygon:Thus the curve leaves $P_0$ toward $P_1$ and arrives at $P_3$ from $P_2$. These nonzero derivatives determine the endpoint tangent lines; if an endpoint derivative vanishes, that formula alone does not determine its tangent direction. Endpoint handles are useful when arranging a parametric first-derivative join of Bézier curves.

The parameter $t$ is usually not arc length. For this example,Equal steps in $t$ therefore do not generally travel equal distances. Distance along the curve is instead the arc length, given by the integral $s(t)={\int }_0^t\Vert C^{\prime }(u)\Vert du$; its derivative is the norm of the tangent vector and measures the rate of travel.

Two geometric facts make Bézier curves especially convenient for design. First, the Bernstein basis weights are nonnegative and form a partition of unity, since the binomial theorem gives ${\sum }_i{b}_{i,n}(t)=((1-t)+t{)}^n=1$. Hence $C(t)$ is a convex combination of the control points and lies in their convex hull.^[ref] The convex hull is the smallest convex set containing the control points, not their axis-aligned bounding box. Here it is a trapezoid, strictly smaller than $[0,4]\times [0,2]$: the box corner $(0,2)$ is outside the convex hull. The curve need not fill or touch every edge of either enclosure. The convex hull guarantee concerns $0\le t\le 1$; outside that interval weights can be negative.

Second, applying an affine map to every control point gives exactly the same result as applying it to the entire curve. For $T(x)=Ax+b$,This is affine equivariance of a geometric basis: a translation, rotation or shear mapping can be performed on a handful of control points. For example, $T(x,y)=(2x+y,y+1)$ transforms the four control points to $(0,1),(4,3),(8,3),(8,1)$ and transforms the midpoint to $(5.5,2.5)$, also obtained from the same weights $(1,3,3,1)/8$.

These editable handles explain the usefulness of Bézier curves in computer aided geometric design, vector graphics paths and outline fonts: a small collection of points controls an entire smooth stroke, and resizing the design preserves its mathematical shape. Cambridge's computer-graphics notes describe their use in graphic design, typography and PostScript outlines. The industrial context includes Pierre Bézier's work at Renault and Paul de Casteljau's work at Citroën.^[ref]

// Target: analysis.bigb

For a doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.

Every doubly stochastic matrix is a convex combination of permutation matrices. Equivalently, the extreme points of the doubly stochastic convex polytope are exactly the permutation matrices. The extreme-point assertion follows from an alternating-cycle perturbation of a doubly stochastic matrix; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.

For an integer $0\le k\le n$, the capped simplexis the convex hull of the zero-one vectors having exactly $k$ entries equal to one. It is a convex polytope whose extreme points are precisely these vectors.

If a feasible vector has a fractional coordinate, the integer coordinate sum forces at least two fractional coordinates. Perturbing one upward and the other downward by a sufficiently small amount gives two distinct feasible vectors whose midpoint is the original vector. It is therefore not an extreme point. Conversely, a zero-one vector cannot be a nontrivial convex combination of points of $[0,1{]}^n$, since each coordinate is already at a bound.

Every point in the convex hull of a subset of ${\mathbb{R}}^d$ is a convex combination of at most $d+1$ points of that subset. Thus in the plane three ingredients always suffice, however many samples were supplied. The representation of $p=(2,1)$ in convex hull illustrates this bound. Two ingredients need not suffice: the centroid of a triangle with only its three vertices as input is on none of their three pairwise line segments.

A short proof outline removes redundant ingredients. With more than $d+1$ points, the augmented vectors $(s_i,1)$ are linearly dependent. A dependence lets the weights vary while preserving both their sum and the represented point. Move along it until one positive weight first becomes zero; all weights stay nonnegative. Repeating leaves at most $d+1$ positive weights.

In his 1911 paper, Constantin Carathéodory used convex geometry to investigate the possible Fourier coefficients of positive harmonic functions. Its introduction interprets convex mixtures through the center of mass, connecting finite-dimensional geometry to constraints on a function's coefficients.^[ref]

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 $n\ge 3$ control points $P_0,\dots ,P_{n-1}$, set $P_n=P_0$ and interpret indices cyclically. One refinement $S$ givesand the new control polygon is the ordered sequenceClose it by joining $R_{n-1}$ back to $Q_0$. Use the old control points for every average in the same refinement; updating them in place would define a different algorithm. One refinement produces $2n$ stored control points, and $k$ refinements produce $2^{k}n$, 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 polygonThe first edge gives $Q_0=\frac{3}{4}(0,0)+\frac{1}{4}(4,0)=(1,0)$ and $R_0=\frac{1}{4}(0,0)+\frac{3}{4}(4,0)=(3,0)$. 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 $16$ control points, and five have $128$. The illustration shows finite control polygons at stages $0,1,2,5$; the last is already visually rounded but still consists of line segments.

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 $H_k$ is the convex hull of the stage-$k$ control points, then $H_{k+1}\subseteq H_k$. 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 $(P_{i-1}+P_i)/2$ to $(P_i+P_{i+1})/2$. Differentiating gives $C_i^{\prime }(0)=P_i-P_{i-1}$ and $C_i^{\prime }(1)=P_{i+1}-P_i$, so adjacent spans have matching values and matching first derivatives. Their second derivatives generally differ. Thus the parameterized curve is $C^1$, generally not $C^2$; degenerate control points can still make its tangent vector vanish. For the rectangle, the span around $P_1=(4,0)$ iswhich rounds the original corner between edge midpoints $(2,0)$ and $(4,1)$. 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 $T(x)=Ax+b$,and the same calculation holds for $R_i$. The sum-to-one weights account for the translation. Therefore $T(S(P))=S(T(P))$ 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 $(x,y)\mapsto (x+y/2,y)$ with the translation $(1,-1)$ to obtain $T(x,y)=(x+y/2+1,y-1)$. The rectangle's control points become $(1,-1),(5,-1),(6,1),(2,1)$. On its right edge, cutting first gives $Q_1=(4,1/2)$ and then $T(Q_1)=(21/4,-1/2)$. Transforming first and cutting instead gives $\frac{3}{4}(5,-1)+\frac{1}{4}(6,1)=(21/4,-1/2)$, the same control point.

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]

The smallest closed convex set containing a set $C$, equivalently the closure of its convex hull in the specified topology. The topology must be stated: the norm topology, weak topology and weak-star topology need not give the same closure for an arbitrary set.

Even a bounded infinite input need not have a closed convex hull. In the real line, let $S=\{1/n:n\ge 1\}$. Every finite convex combination of these positive points is positive, so zero is absent. Conversely, any $x\in (0,1]$ lies between some $1/n$ and $1$, and is their convex combination. HenceThe closed convex hull adds the missing limit point zero. For the finite eight-point example in convex hull, the convex hull is already closed, so taking the closed convex hull adds nothing.

In a Banach space, the closed convex hull of a compact set is compact in the norm topology. Given $\epsilon >0$, choose a finite $\epsilon$-net $\{y_i\}$ for $K$. Every convex combination of points of $K$ is within $\epsilon$ in norm of $\mathrm{conv}\{y_i\}$, by replacing its terms by their approximating $y_i$. This finite-dimensional compact convex set has a finite $\epsilon$-net, giving a finite $2\epsilon$-net for $\mathrm{conv}K$. Its closure is therefore totally bounded and complete, hence compact. Completeness of the ambient space is used at this last step.

A finite sum ${\sum }_j{\lambda }_j{s}_j$ with ${\lambda }_j\ge 0$. Unlike a convex combination, the coefficients need not sum to one. Zero coefficients and the empty sum are allowed.

For a parametric curve represented by fixed scalar functions $b_j$ and control points $P_j$ in Euclidean space, writeThe influence function of this handle is $b_i$: the resulting displacement vector is $\Delta C(t)=\tilde{C}(t)-C(t)=b_i(t)h$, and its norm is $|b_i(t)|\Vert h\Vert$. These are exact finite changes, not only a first-order estimate. Where $b_i$ is negative the displacement points opposite to $h$. Where $b_i(t)=0$, the curve is unchanged at that parameter.

For the cubic Bézier curve above, the Bernstein basis influence function is $b_{1,3}(t)=3t(1-t{)}^2$. Its derivative isIt increases up to $t=1/3$ and decreases thereafter on $[0,1]$. Consequently the largest displacement at corresponding parameters isFor $h=(0,1)$ it is $4/9$. This is a comparison at the same parameter. A geometric closest-distance comparison, as in a closest-point search on a subdivision curve, instead minimizes over another parameter:The closest parameter $s$ can differ from $t$, so $4/9$ is not automatically a maximum closest-distance separation of the two curves. Neither parameter is assumed to be arc length.

The support of a function $b_i$ is the closure of the parameter values where $b_i\ne 0$. It bounds where a nonzero handle move can act, but may include boundary points where the actual displacement is zero. Here the support of a function $b_{1,3}$ is all of $[0,1]$ relative to the parameter domain, while the endpoints are unaffected. In contrast, a B-spline of order $k$ has support within $[t_i,t_{i+k}]$ in its spline knot sequence, so its handle affects only that parameter range; the support and Gram bandwidth of B-splines describes the same locality in another application. Changing the spline knots or the basis along with the handle requires a different comparison.

When the basis functions form a partition of unity, ${\sum }_j{b}_j(t)=1$, each evaluation is an affine combination of the control points. Applying an affine map $T(x)=Ax+a$ to all handles givesThis is affine equivariance of a geometric basis, also called affine covariance: affine maps preserve affine combinations. In particular, translating every handle by $h$ translates the whole curve by $h$, whereas moving just one handle produces $b_i(t)h$. The Bernstein basis has this partition of unity property.^[ref] Nonnegative weights further make evaluations convex combinations, giving the convex hull bound illustrated by the control polygon; nonnegativity is not needed for affine covariance.

For a proof outline of the influence formula, subtract the two basis representations: every unchanged coefficient cancels, leaving $b_i(t)(P_i+h)-b_i(t)P_i=b_i(t)h$. The same subtraction with several moved handles gives $\Delta C(t)={\sum }_i{b}_i(t)h_i$. No claim about interpolation, closest-point search on a subdivision curve or endpoint motion follows until the actual basis values are examined.

A convex block of a sequence in a Banach space is a sequence of convex combinations supported on successively disjoint finite intervals, with $p_n<q_n<p_{n+1}$, $a_i\ge 0$, and ${\sum }_{i=p_n}^{q_n}{a}_i=1$. Zero coefficients can fill gaps and ensure strict endpoint inequalities. By the Mazur theorem, every weakly null sequence has convex blocks tending to zero in norm.

The greatest convex function lying below a given function, when such an envelope is considered in the specified domain. A convex combination of phase compositions and their Gibbs free energies constructs candidate mixtures; the equilibrium free energy is their lower convex envelope. For two differentiable coexisting branches, the supporting line is a common tangent.

Consider a stipulated continuous-allocation problem. Amounts $x,y$ of two activities use $x+2y$ units of a common resource, with budget six. The feasible regionis a triangle with extreme points $(0,0)$, $(6,0)$ and $(0,3)$. It is the intersection of three closed half-spaces, hence a closed convex set. The general intersection argument is short: a line segment between two points in every constraint set belongs to every constraint set, so it belongs to their intersection.^[ref]

For an original numerical check, take $A=(1,2)$ and $B=(5,1/4)$. Their resource totals are $5$ and $11/2$. Every convex combination $Z(t)=(1-t)A+tB$ is nonnegative and has resource totalIn particular the midpoint is $(3,9/8)$, using $21/4$ units. This verifies the full line segment, rather than just a plotted sample of it.

This is useful whenever divisible quantities share linear limits: the feasible choices remain compatible under averaging. A new linear equation also preserves this property, because averaging two identical constraint values gives the same value. The affine subspace and closed half-space viewpoints explain this without requiring a separate argument for every budget.

The convex hull of a set consists of every finite convex combination of its points. It collects all choices obtainable by mixing the original choices with nonnegative weights summing to one. For $S$ in a real vector space,Equivalently this is the smallest convex set containing $S$. Mixing two already mixed points produces another finite convex combination, so the displayed set is convex; every convex set containing $S$ must contain all these mixtures.^[ref]

In an original planar example, take four points $A=(0,0)$, $B=(4,0)$, $C=(3,3)$, $D=(0,2)$ and four additional samples $(1,1)$, $(2,1.7)$, $(3,0.5)$, $(1,0.5)$. Their convex hull is the filled convex polygon $ABCD$, including its boundary. None of the samples is $p=(2,1)$, butThe coefficients are nonnegative and sum to one, providing an explicit membership certificate. Geometrically, first form $U=(3/2,0)=\frac{5}{8}A+\frac{3}{8}B$ on the line segment $AB$, then mix $p=\frac{2}{3}U+\frac{1}{3}C$. The additional interior samples do not enlarge the convex hull.

For a finite nonempty $S\subset {\mathbb{R}}^d$, the convex hull is the image of a probability simplex of weights under the linear map $\lambda \mapsto {\sum }_i{\lambda }_i{s}_i$. The probability simplex is a compact set, and the map is continuous, so this convex hull is compact and closed. A one-point input stays one point; a collinear input stays in a line segment. Filling the convex hull does not necessarily produce a full-dimensional region.

The construction is useful whenever mixtures preserve the intended meaning of a choice. Mixing resource-allocation vectors, for example, interpolates their coordinate requirements. The convex hull describes the resulting feasible region. A coordinate-wise box can admit combinations that no mixture produces, as the outside-point certificate in linear optimization on a convex hull shows.

By Stephen Boyd, Lieven Vandenberghe.

Publisher: Cambridge University Press.

Online text: www.seas.ucla.edu/~vandenbe/cvxbook/bv_cvxbook.pdf

Cited passages: Appendix A.5.2, pp. 646–647: symmetric eigenvalue decomposition and definiteness; §2.2.2, p. 30, equation (2.3): ellipsoids and semi-axis lengths; the book uses the inverse quadratic coefficient matrix; §3.1.4, Example 3.2, p. 71: a quadratic function is strictly convex exactly when its symmetric coefficient matrix is positive definite.

Online text: stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

Cited passages: Appendix A.5.5, printed p. 650: block inversion and minimized quadratic form; §C.4.1, printed pp. 672–675: block elimination, Algorithm C.4, factor-solve interpretation and dense complexity.

Online text: web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

The front matter states first publication in 2004 and a seventh printing with corrections in 2009. The title page credits Stephen Boyd and Lieven Vandenberghe as whole-book coauthors; no separate appendix byline is supplied. Cambridge University Press publishes the book; the Stanford author website hosts this copy.

Cited passages: Appendix A.1.6, printed pp. 636–637, dual norms.

Additional cited passage: §2.1.4, printed p. 24 (PDF page index 37), convex combinations and the definition and minimality of the convex hull. The title-page whole-book credits and the separately recorded 2004 first publication and 2009 corrected seventh printing apply to this copy.

Additional cited passages: §5.6.3, printed pp. 251–253, especially equation (5.58), local sensitivity of the optimal value to equality-constraint perturbations. The sign of the Lagrange multiplier depends on the chosen sign for the equality term. The title page and front matter retain the whole-book authorship, 2004 first publication and 2009 corrected seventh printing recorded above.

Additional locators: §§5.1–5.2, pp.215–227.

For the two-dimensional heat equation with zero Dirichlet boundary conditions, the Crank-Nicolson diffusion scheme preserves the interval between the minimum and maximum of the initial nodal values and zero under the displayed restriction. The old-time coefficients form a convex combination, while the new-time matrix has positive diagonal, nonpositive off-diagonal entries and row diagonal-dominance margin one. A hypothetical new value above the old maximum makes the new-time row at least that value while its right side is at most the old maximum, a contradiction; apply the reversed inequality at a new minimum. In particular initial nonnegative or nonpositive values preserve their sign. The step restriction guarantees these value bounds even though scalar A-stability holds without it.

De Casteljau's algorithm evaluates a Bézier curve by repeated linear interpolation between neighboring control points. Fix $t\in [0,1]$, start with $P_i^{(0)}(t)=P_i$, and computeEach new row has one fewer point. The final point is $P_0^{(n)}(t)=C(t)$. Use the same $t$ at every stage: it describes the fraction of each line segment traversed from its first endpoint toward its second. A cubic Bézier curve needs three levels containing $3$, $2$, and $1$ linear interpolations, respectively.^[ref]

For the Bézier curve with control points $P_0=(0,0)$, $P_1=(1,2)$, $P_2=(3,2)$, $P_3=(4,0)$, evaluation at $t=1/2$ takes the midpoint of every neighboring pair. The first level givesThe second level givesand the third level givesThe intermediate control polygons shrink toward the evaluated point. Each step is a convex combination, giving a geometric explanation of the convex hull property; every step also commutes with an affine map.

The same construction splits the Bézier curve exactly, with no approximation. The outer edges of the triangular array give the new control points: for a cubic, $(P_0,Q_0,R_0,S)$ specify the left piece and $(S,R_1,Q_2,P_3)$ specify the right piece.^[ref] At $t=1/2$ these two lists areWrite $C_L$ and $C_H$ for the Bézier curves defined by these lists, each with its own parameter $u\in [0,1]$. ThenTheir images reproduce the original curve, while their derivatives account for the shorter parameter intervals. At the join,The chain rule gives $C_L^{\prime }(1)=C_H^{\prime }(0)=C^{\prime }(1/2)/2$; in the original parameter, both pieces have derivative $(4.5,0)$. This is the interval scaling in the parametric first-derivative join of Bézier curves.

Repeated midpoint splitting is useful for drawing vector graphics paths: each piece has a smaller control polygon and its own convex hull enclosure. A renderer can refine pieces until they are sufficiently close to line segments at the chosen display scale. Evaluating $C(t)$ and splitting it are thus two results of the same short algorithm.

For a proof outline, expanding the recursion givesPascal's identity proves this by induction; at $r=n$, $i=0$ it is precisely the Bernstein basis formula for the Bézier curve. The geometric construction remains useful even when expanding the polynomial by hand would be cumbersome.

// Target: analysis.bigb