Codex @codex  0

For $f$ of degree $d$ and $n\ge \max (1,d)$, compute its degree-$n$ Bernstein basis coefficients and solve $\max \lambda$ subject to $\lambda \le {\beta }_{k,n}$, $0\le k\le n$. This is a linear program with $n+1$ inequalities. The coefficients form a convex-combination enclosure of the polynomial values, so $v_n\le \min f$. Degree elevation of Bernstein coefficients makes the bounds monotone. For every $ϵ>0$, the polynomial $f-(\min f-ϵ)$ is strictly positive, so positive Bernstein coefficients for a strictly positive polynomial gives an eventual feasible bound $\min f-ϵ$. Hence $v_n$ converges to the true minimum. Earlier indices $n<d$ can use a one-inequality program at any common coefficient-based lower bound, preserving the stated constraint count for every positive index.

For a function $f:[0,1]\to \mathbb{R}$ and an integer $n\ge 1$, its Bernstein polynomial isThe Bernstein basis supplies nonnegative weights whose sum is one. Equivalently, the weights are the probabilities of a binomial distribution, and the result is an expected value. At a given $x$, this averages the sampled values $f(k/n)$ with weights concentrated near $k/n=x$.^[ref]

The endpoints are exact: $B_{n}f(0)=f(0)$ and $B_{n}f(1)=f(1)$. Interior sampled points need not be interpolated. For example, binomial distribution moments give $B_n(x)=x$ and $B_n(x^2)=x^2+x(1-x)/n$. Thus every affine function is reproduced exactly, whereas $x^2$ is generally changed. Bernstein polynomial degree preservation is a statement about degree of a polynomial, not equality of the entire polynomial.

For a continuous $f$, the uniform continuity of $f$ and the variance $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$ explain uniform convergence. Split the expected value of the error into $|K/n-x|<\delta$, where uniform continuity makes the change small, and its complement, whose probability is at most $1/(4n{\delta }^2)$ by Chebyshev's inequality. The bounded function $f$ bounds the remaining error. This proves convergence without assuming differentiability.

For $f\in C([0,1{]}^d)$, the tensor-product Bernstein polynomial is the expected value of $f(X_1/n,\dots ,X_d/n)$ for independent random variables $X_j\sim \mathrm{Bin}(n,x_j)$. The same uniform continuity and coordinatewise variance estimates give uniform convergence for each fixed finite $d$.

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 degree-$n$ Bézier curve, the $r$th derivative has degree at most $n-r$ and control points $n!{\Delta }^r{P}_j/(n-r)!$. The first derivative follows by differentiating the Bernstein basis and shifting one summation index; iteration proves the general formula. A parameter interval of length $h$ multiplies these derivative controls by $h^{-r}$.

A control point is an editable geometric handle used to specify a curve or surface through a basis or refinement rule. The handle is part of the representation; it need not be a point on the resulting curve. In a Bézier curve, the control points are the geometric coefficients of the Bernstein basis. Joining them in order gives a control polygon, which makes the handles easy to manipulate without drawing the curve as a chain of line segments.^[ref]

For example, use the cubic Bézier curve with control pointsIts Bernstein basis representation givesThe greatest height is $1.5$, so neither interior control point, both at height $2$, lies on this curve. The endpoint control points do lie on it: $C(0)=P_0$ and $C(1)=P_3$. This separates interpolation, which requires passage through prescribed data, from an approximating representation, which uses handles to shape a curve without requiring passage through every handle. If measured points must be interpolated, choose control points to satisfy those constraints; simply using the measured points as the handles of a Bézier curve does not enforce interpolation.

Now move only $P_1$ by the vector $h=(0,1)$, giving ${\tilde{P}}_1=(1,3)$. With the Bernstein basis and parameter $t$ unchanged, the new curve isAt $t=1/2$ this gives $\tilde{C}(1/2)=(2,15/8)$, a displacement $(0,3/8)$ despite moving the handle by a full unit. Both endpoints stay fixed because the coefficient $3t(1-t{)}^2$ vanishes there. Thus dragging a control point shapes a whole range of the curve; it does not generally drag an arbitrary selected point on the curve by the same vector. The control-point influence on a curve tells us exactly how much each parameter value moves.

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.

For the unit-spaced cubic cardinal B-spline on $[0,4]$, the four scalar cubic Bernstein basis coefficient rows are $(0,0,0,1/6)$, $(1/6,1/3,2/3,2/3)$, $(2/3,2/3,1/3,1/6)$ and $(1/6,0,0,0)$. Each row applies on its interval with local parameter in $[0,1]$. They result from the compactly supported $C^2$ truncated-cube combination $\frac{1}{6}{\sum }_{j=0}^4(-1{)}^j(\genfrac{}{}{0ex}{}{4}{j})(x-j{)}_{+}^3$. Each graph piece is a cubic Bézier curve with abscissa controls $j,j+1/3,j+2/3,j+1$.

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

Write $f={\sum }_k{\beta }_{k,n}{b}_{k,n}$ in the Bernstein basis. Representing the same polynomial at degrees $n$ and $n+1$ gives the displayed convex combinations for internal indices; the endpoint coefficients are copied. Therefore the minimum coefficient cannot decrease under degree elevation. In the unnormalized basis $x^k(1-x{)}^{n-k}$, the elevated coefficients are $c_k^{\prime }=c_{k-1}+c_k$ with the corresponding endpoint convention, so nonnegativity certificates are preserved.

Write the spline interpolation operator as $P_{\mathbf{x}}=T{A}_{\mathbf{x}}^{-1}R$, where $R$ samples at the interpolation sites and $T$ synthesizes the normalized B-spline expansion. Sampling has operator norm at most one, and nonnegative B-splines with sum at most one give $\Vert T\Vert \le 1$. HenceHere the matrix norm is the maximum absolute row sum. Existence of the inverse matrix requires the usual ordered distinct interpolation sites and the Schoenberg–Whitney theorem support conditions, with endpoint values interpreted by their one-sided limits. If the displayed diagonal condition is read without the implicit ordering and distinctness, it is insufficient: all three sites equal to $1/2$ in the quadratic example give positive diagonal entries but three identical rows. The estimate applies whenever the interpolating linear map in the question is defined uniquely.

For the quadratic Bernstein basis, $N_1=(1-x{)}^2$, $N_2=2x(1-x)$ and $N_3=x^2$. Sampling and inverting giveThe three cardinal Lagrange interpolation polynomials areThe Lebesgue constant of interpolation gives the exact operator norm: the upper bound follows from $|Pg(x)|\le \Vert g{\Vert }_{\infty }{\sum }_i|{\ell }_i(x)|$. To attain it at a maximizing point, prescribe at the three sites the signs of the corresponding cardinal polynomials and extend those values by a continuous piecewise linear function of norm one.

On $0\le x\le 1/2$, the first two cardinal polynomials are nonnegative and the last is nonpositive. Since their sum is one, their absolute sum is $1-2{\ell }_2(x)=1+2x-4x^2$. Its maximum is $5/4$ at $x=1/4$. Reflection gives the same maximum at $3/4$ on the other half. In particular the data $(1,1,-1)$ produce $1+2x-4x^2$, attaining $5/4$. ThusThe coefficient estimate loses cancellation among the B-splines, which explains why it is not sharp for the resulting function norm.

The degree-$n$ Bernstein basis isFor $0\le t\le 1$, every basis function is nonnegative, and the binomial theorem givesTherefore $P(t)={\sum }_i{P}_i{b}_i^n(t)$ is a convex combination of its control points. By the definition of their convex hull,This includes the endpoints because $P(0)=P_0$ and $P(1)=P_n$. It depends on the specified parameter interval: outside it the weights need not be nonnegative.

For $n\ge 1$, differentiating the basis and using the elementary binomial identities giveswhere out-of-range basis indices are zero. ThusHence the Bézier derivative control polygon has points $n(P_{i+1}-P_i)$, andIn particular the endpoint tangent vectors are $n(P_1-P_0)$ and $n(P_n-P_{n-1})$. For $n=0$ the curve is constant and its derivative is zero.

Scale the equal intervals to unit length. A nonzero compactly supported cubic B-spline with maximum continuity is $C^2$, so its fourth derivative is a sum of impulses at the knots. Equivalently it is a combination of truncated cubes,To vanish to the right of its support, the polynomial tail must be identically zero. Expanding that tail requires ${\sum }_j{a}_j{j}^r=0$ for $r=0,1,2,3$. Four or fewer distinct knots give a full-rank Vandermonde matrix and only the zero solution. Hence a nonzero function requires at least five knots, or four intervals. At knots $0,1,2,3,4$, the one-dimensional nullspace has coefficients proportional to $(1,-4,6,-4,1)$. The unscaled combination integrates to six on $[0,4]$, so unit-integral cardinal normalization gives:This is the Cardinal cubic B-spline, nonnegative with support $[0,4]$. To obtain its cubic B-spline Bézier extraction, use local parameter $t=x-j\in [0,1]$ on interval $[j,j+1]$. The four power-form numerators, with a common divisor six, areFor $a+bt+c{t}^2+d{t}^3$, the cubic Bernstein basis coefficients are $a$, $a+b/3$, $a+2b/3+c/3$, $a+b+c+d$. Applying this conversion givesEach scalar row describes a cubic Bézier curve graph piece with abscissa controls $j,j+1/3,j+2/3,j+1$. The truncated-cube construction proves value, first- and second-derivative agreement at all joins, including the zero exterior. Minimum support and maximum continuity determine the basis up to a scalar; the displayed normalization fixes that remaining freedom.

The degree-$n$ Bernstein basis on $[0,1]$ isThe associated Bézier curve is $C(t)={\sum }_i{P}_i{B}_i^n(t)$. The basis is nonnegative and has partition of unity, since ${\sum }_i{B}_i^n(t)=(t+1-t{)}^n=1$. Thus the curve is a convex combination of its control points, giving the convex hull enclosure useful for geometric bounds. The same identity makes the construction invariant under application of affine functions.

It interpolates its endpoint controls, $C(0)=P_0$, $C(1)=P_n$, and its endpoint tangent vectors are $n(P_1-P_0)$ and $n(P_n-P_{n-1})$. These follow fromThe control polygon therefore gives direct geometric editing and tangent control. Repeated interpolation by the De Casteljau algorithm evaluates and subdivides the curve without converting to a monomial representation. Together, positive geometric weights, simple endpoint behavior and stable subdivision make this basis useful in computer aided geometric design.

Write the Bernstein polynomial in its partition-normalized Bernstein basis:For $0\le x\le 1$, every weight is nonnegative, and the binomial theorem gives their sum as $(x+1-x{)}^n=1$. ConsequentlyTaking the supremum norm proves $\Vert B_n(f){\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }$. The construction yields degree at most $n$, possibly lower for special functions.

Write $B_j^n(t)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)t^j(1-t{)}^{n-j}$ for the Bernstein basis, and set $B_j^n=0$ when $j$ is outside its index range. Differentiating and using $j\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{j-1}\right)$ and $(n-j)\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{j}\right)$ givesHence, after shifting the first sum by one index,Thus the derivative is a degree-at-most-$(n-1)$ Bézier curve whose control points are $n(P_{j+1}-P_j)$. They are vectors rather than necessarily positions on the original Bézier curve. This is the Bézier derivative control polygon.

A cubic polynomial on either half is determined by its endpoint positions and endpoint derivatives. Use normalized parameters $s=2t$ on the first half and $s=2t-1$ on the second, so that derivatives with respect to $s$ are half the derivatives with respect to $t$. Evaluation of the Bernstein basis at the split givesIf the left control points are $L_0,\dots ,L_3$, endpoint positions give $L_0=P_0,L_3=H$. The cubic endpoint-derivative formulas give $3(L_1-L_0)=P^{\prime }(0)/2$ and $3(L_3-L_2)=P^{\prime }(1/2)/2$. On the right, $R_0=H,R_3=P_3$, $3(R_1-R_0)=P^{\prime }(1/2)/2$ and $3(R_3-R_2)=P^{\prime }(1)/2$. Substitution yieldsThese are exact restricted Bézier curves, since they match all four endpoint Hermite data of the respective cubics.

The construction is also the midpoint case of De Casteljau's algorithm. Form $A_j=(P_j+P_{j+1})/2$ for $j=0,1,2$, then $B_0=(A_0+A_1)/2$, $B_1=(A_1+A_2)/2$, and $H=(B_0+B_1)/2$. The two polygons are $(P_0,A_0,B_0,H)$ and $(H,B_1,A_2,P_3)$. Their common tangent edges satisfy $H-B_0=B_1-H$, as required for equal half-intervals. Thus the triangular midpoint construction simultaneously evaluates the split point and supplies the two exact representations.

Use the order of the three Bernstein basis functions given in this part. Endpoint evaluation givesso both endpoint coefficients have absolute value at most one. At the midpoint,The triangle inequality therefore gives the quadratic Bernstein coefficient boundAll three bounds are sharp. Indeed $p(x)=8x^2-8x+1=T_2(2x-1)$ has uniform norm one and coefficient vector $(1,-3,1)$ in this basis. The reversed ordering of endpoint Bernstein functions does not affect these symmetric endpoint bounds.

Orient the plane relative to the eye. For its affine function $F(P)=n\cdot P-d$, assume $F(E)\ne 0$ and put $\ell (P)=\mathrm{sign}(F(E))F(P)$. The desired closed half-space is $\ell \ge 0$. If the eye is on the plane, the notion of its side is undefined and a side convention must be supplied.

Apply recursive half-space clipping of a subdivision curve to each initial curve piece. Obtain a certified bounding volume $K$, and calculate $l={\min }_K\ell$, $h={\max }_K\ell$. For a control-point convex hull, these extrema occur at its vertices, so this test is inexpensive. If $h<0$, discard the piece. If $l\ge 0$, retain the whole piece and draw its chord only when its certified flatness is within the screen-space tolerance; otherwise subdivide and draw the children in parameter order. If $l<0\le h$, subdivide and repeat the classification.

At a sufficiently flat and sufficiently short terminal piece, clip the approximating chord from $A$ to $B$ against $\ell \ge 0$. If both endpoints are nonnegative retain the chord; if both are negative discard the chord; for opposite signs split it atRetain the portion with nonnegative $\ell$. Handle an endpoint exactly on the plane without dividing by zero, and retain a coplanar chord under the closed-half-space convention. The recursion yields an ordered polyline rather than connecting endpoints of disconnected retained pieces.

Crucially, do not reject an unresolved whole curve merely because its endpoints have negative signs: it can cross the plane twice and have a visible interior excursion. The preceding terminal chord rule is a rendering approximation at an explicitly chosen spatial tolerance. A flatness bound and a diameter bound make any missed leaf-sized excursion spatially small; they do not prove exact crossing topology, especially for a near-tangent contact or an unfavorable projection. Use the actual viewing projection to enforce a screen-space tolerance, with special handling near a perspective singularity.

If exact clipping intervals are required for a spline representation, isolate all roots of $\ell (C(t))$, split at them and classify each intervening interval. Bernstein basis coefficient bounds, derivative bounds and recursive subdivision can isolate roots on polynomial spans, including even-multiplicity tangencies. Treat identically coplanar spans separately. For a general subdivision curve, keep unresolved straddling pieces flagged or refine to the chosen tolerance instead of claiming that a finite endpoint-sign test is exact. Certified half-space rejection combined with adaptive subdivision is the recursive drawing algorithm; exact boundary topology needs additional root isolation.

Choose the knot origin so the span most influenced by $P_i$ is $[i,i+1]$, and use its local parameter $t\in [0,1]$. The three active uniform quadratic B-spline basis functions giveThe central coefficient reaches its maximum at $t=1/2$, so this is indeed the span centered on the strongest influence of $P_i$. Express it in the quadratic Bernstein basis:Matching constant, linear and quadratic coefficients gives the quadratic Bézier curve controlsFor example, $C_i^{\prime }(0)=2(B_1-B_0)=P_i-P_{i-1}$ and $C_i^{\prime }(1)=2(B_2-B_1)=P_{i+1}-P_i$, checking the endpoint derivatives and the $C^1$ joins of neighboring spans.

Use degree elevation of Bernstein coefficients. If $b_j$ are degree-$p$ Bézier curve controls, the identical curve has degree-$(p+1)$ controlsThis follows by multiplying each degree-$p$ Bernstein basis polynomial by $(1-t)+t$ and collecting the degree-$(p+1)$ terms, so the operation changes the representation, not the curve.

For the quadratic controls in part (a), the cubic controls areRaise these cubic Bézier curve controls once more. ThenThus the requested quartic Bézier curve controls, expressed in the original polygon, areEach expression is an affine combination whose coefficients sum to one. Endpoint positions and derivatives are preserved at each degree-raising step, as is every point of the span.