# De Casteljau's algorithm

**De Casteljau's algorithm** is a recursive method for evaluating a point on a [Bézier curve](https://www.edgepedia.org/bezier-curve) from its control points by repeated linear interpolation. Given \( k+1 \) control points \( p_0, \ldots, p_k \) and a parameter \( t \in [0,1] \), it computes the curve point through the recurrence

\[ \beta^0_i(t) := p_i, \qquad \beta^r_i(t) := (1-t)\,\beta^{r-1}_i(t) + t\,\beta^{r-1}_{i+1}(t), \quad r = 1, \ldots, k, \;\; i = 0, \ldots, k-r, \]

and the value \( \beta^k_0(t) \) is the point on the curve at \( t \)<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>. The result is the polynomial curve with coefficients \( p_0, \ldots, p_k \) expanded in the Bernstein basis (polynomial basis used to represent Bézier curves) \( b^k_j(t) = \binom{k}{j}(1-t)^{k-j}t^j \)<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>. The algorithm is a fundamental tool for computing Bézier curves in computer-aided geometric design (CAGD) and computer graphics<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>.

| Key fact | Detail |
|---|---|
| What it computes | The point of a Bézier curve at parameter \( t \) from \( k+1 \) control points, by \( k \) rounds of linear interpolation ("corner cutting")<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup> |
| Origin | Developed by Paul de Faget de Casteljau at Citroën; his 1963 SA notes show the algorithm applied to a cubic<sup>[2](https://www.researchgate.net/profile/James-Peters-3/post/Since_the_Bernstein_basis_is_more_stable_than_the_1_x_x2_x3_basis_why_do_we_use_the_second_one/attachment/59d62e4cc49f478072e9ef35/AS%3A273573887840257%401442236505726/download/Farouki-on-Berstein-basis-2012.pdf)</sup> |
| Stability | Unconditionally numerically stable for \( t \) in the parameter interval; unstable outside it, with error growing polynomially in the distance outside<sup>[3](https://courses.physics.illinois.edu/cs418/fa2022/text/bezier.html)</sup> |
| Cost | Quadratic in the number of control points, linear storage, both multiplied by the dimension \( d \)<sup>[4](https://onlinelibrary.wiley.com/doi/10.1111/cgf.70403)</sup> |
| Subdivision | The intermediate points are the control points of the two curve segments on \( [0,t] \) and \( [t,1] \)<sup>[2](https://www.researchgate.net/profile/James-Peters-3/post/Since_the_Bernstein_basis_is_more_stable_than_the_1_x_x2_x3_basis_why_do_we_use_the_second_one/attachment/59d62e4cc49f478072e9ef35/AS%3A273573887840257%401442236505726/download/Farouki-on-Berstein-basis-2012.pdf)</sup> |
| Extensions | Rational Bézier curves via homogeneous coordinates; Bézier surfaces; polar forms (blossoms)<sup>[5](https://citeseerx.ist.psu.edu/document?doi=fca198bee49c67521579e7d9aea4da2b13dc6d62&repid=rep1&type=pdf)</sup><sup> • </sup><sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup> |

## How the recursion works

Each step of the algorithm is a linear interpolation, often called a lerp: the point \( (1-t)p_i + t\,p_{i+1} \) lies on the segment between two consecutive points, at the fraction \( t \) of the way from the first to the second<sup>[3](https://courses.physics.illinois.edu/cs418/fa2022/text/bezier.html)</sup>. Starting from the control polygon, one round replaces \( k+1 \) points by \( k \) points on its edges; repeating \( k \) times leaves a single point, which equals the curve value \( \beta(t) \)<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>. Because each round removes one vertex, the scheme is an example of a "corner-cutting" algorithm<sup>[2](https://www.researchgate.net/profile/James-Peters-3/post/Since_the_Bernstein_basis_is_more_stable_than_the_1_x_x2_x3_basis_why_do_we_use_the_second_one/attachment/59d62e4cc49f478072e9ef35/AS%3A273573887840257%401442236505726/download/Farouki-on-Berstein-basis-2012.pdf)</sup>.

For a cubic curve with control points \( p_0, p_1, p_2, p_3 \), the first round produces three points \( r_i \), the second two points \( s_i \), and the third the single point \( t_0 = q(u) \)<sup>[6](https://mathweb.ucsd.edu/~sbuss/MathCG2/SecondEdDraft.pdf)</sup>. At the midpoint \( u = 1/2 \) every interpolation is a simple average, and the curve point is \( \frac{1}{8}p_0 + \frac{3}{8}p_1 + \frac{3}{8}p_2 + \frac{1}{8}p_3 \)<sup>[6](https://mathweb.ucsd.edu/~sbuss/MathCG2/SecondEdDraft.pdf)</sup>.

## Subdivision

The same computation that evaluates the curve also splits it. The points generated along the left edge of the triangular scheme, \( p^0_0, p^1_0, p^2_0, \ldots, p^n_n \), are the control points of the subsegment on \( [0, \tau] \), and the points along the right edge, read in reverse order, are the control points of the subsegment on \( [\tau, 1] \), each considered as an individual Bézier curve over the full parameter domain \( [0,1] \)<sup>[2](https://www.researchgate.net/profile/James-Peters-3/post/Since_the_Bernstein_basis_is_more_stable_than_the_1_x_x2_x3_basis_why_do_we_use_the_second_one/attachment/59d62e4cc49f478072e9ef35/AS%3A273573887840257%401442236505726/download/Farouki-on-Berstein-basis-2012.pdf)</sup>.

**Recursive subdivision** is the standard way to draw a Bézier curve: split it at \( t = 0.5 \), then split each half again, stopping when a sub-curve is flat enough to be replaced by a straight line segment between its endpoints<sup>[7](https://facultyweb.cs.wwu.edu/~wehrwes/courses/csci480_21w/spline_lab/)</sup>. Subdivision also supports clipping to a boundary and curve refinement<sup>[8](https://people.eecs.berkeley.edu/~sequin/CS284/LEC98/L3.htm)</sup>, and it underlies root-finding methods for the polynomial equations arising in continuous collision detection, alongside Bézier clipping<sup>[9](https://pmc.ncbi.nlm.nih.gov/articles/PMC4283478/)</sup>. A degree-\( n \) curve in \( d \) dimensions can be subdivided in \( O(dn^2) \) time, and a modified algorithm achieves \( O(dn \log n) \) with good numerical quality<sup>[10](https://arxiv.org/abs/2509.15691)</sup>.

## Numerical stability

Within the parameter interval \( t_0 \le t \le t_n \), de Casteljau's algorithm is unconditionally numerically stable: it returns the polynomial value with as much precision as the control points and \( t \) values themselves carry. Outside that interval it still works in principle but accumulates error at a rate polynomial in the distance outside<sup>[3](https://courses.physics.illinois.edu/cs418/fa2022/text/bezier.html)</sup>. Textbook treatments conclude that the method is preferable to conventional polynomial evaluation, including [Horner's method](https://www.edgepedia.org/horners-method), for computer calculation<sup>[6](https://mathweb.ucsd.edu/~sbuss/MathCG2/SecondEdDraft.pdf)</sup>.

The stability reflects the Bernstein basis itself. The basis is optimally suited for polynomial evaluation and is typically more accurate than the monomial basis; the de Casteljau round-off error bound grows only linearly with degree even though the operation count grows quadratically<sup>[11](https://arxiv.org/abs/1808.10387)</sup>. Systematic backward and forward error analyses show that de Casteljau-type algorithms are numerically stable under imprecise arithmetic or perturbed input data, and that Bernstein-type bases are optimally stable for evaluation among all bases of the generated spaces formed by nonnegative functions<sup>[12](https://www.sciencedirect.com/science/article/pii/S0167839623000754)</sup>.

**Limits of the plain algorithm.** When the evaluation problem itself is ill-conditioned, for example near a multiple root of the polynomial, the plain algorithm can return results arbitrarily less accurate than the working precision \( \mathbf{u} \)<sup>[11](https://arxiv.org/abs/1808.10387)</sup>. Compensated variants repair this: applying error-free transformations to track round-off at each stage yields a compensated de Casteljau algorithm whose result is as accurate as if computed in twice the working precision, and a \( K \)-fold compensated version satisfies

\[ \frac{\lvert p(s) - \mathtt{CompDeCasteljauK}(p,s,K) \rvert}{\lvert p(s) \rvert} \le \mathbf{u} + \operatorname{cond}(p,s) \times \mathcal{O}(\mathbf{u}^{K}), \]

that is, accuracy equivalent to running the plain algorithm in \( K \) times the working precision<sup>[11](https://arxiv.org/abs/1808.10387)</sup>. The non-compensated form requires \( 3T_n + 1 \) flops for degree \( n \), where \( T_n \) is the \( n \)th triangular number<sup>[11](https://arxiv.org/abs/1808.10387)</sup>.

## Cost and faster alternatives

The algorithm is quadratic in the number of control points and requires linear storage, both multiplied by the dimension \( d \)<sup>[4](https://onlinelibrary.wiley.com/doi/10.1111/cgf.70403)</sup>. This \( O(n^2 d) \) cost is its main drawback, and algorithms with linear \( O(nd) \) complexity have been proposed that retain its geometric and numerical qualities<sup>[13](https://www.sciencedirect.com/science/article/abs/pii/S0167839624000116)</sup>. Despite the higher cost than Horner's method, it is considered more useful for design purposes<sup>[14](https://www.sciencedirect.com/science/article/abs/pii/S0096300304004795)</sup>.

## Extensions

**Rational curves.** Lifting the control points to homogeneous coordinates, with a weight \( w_i \) per point, lets the de Casteljau algorithm evaluate and subdivide rational Bézier curves, which can represent conic sections; the projection into affine space is applied at the end<sup>[5](https://citeseerx.ist.psu.edu/document?doi=fca198bee49c67521579e7d9aea4da2b13dc6d62&repid=rep1&type=pdf)</sup>. This homogeneous form becomes numerically unstable when the weights differ greatly, and a rational variant of the algorithm is used instead<sup>[5](https://citeseerx.ist.psu.edu/document?doi=fca198bee49c67521579e7d9aea4da2b13dc6d62&repid=rep1&type=pdf)</sup>.

**Surfaces and blossoms.** The algorithm extends to triangular and quadrangular nets, giving evaluation schemes for Bézier surfaces<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>. A further extension yields polar forms, or blossoms, which are particularly useful in the theoretical analysis of Bézier splines and the algorithms that compute them<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>. The knot insertion algorithm for B-spline curves is essentially equivalent to the subdivision algorithm studied for de Casteljau's algorithm<sup>[15](https://dcain.etsin.upm.es/~leonardo/etema4.htm)</sup>.

**Manifold-valued curves.** Because each step is a constructive interpolation, the algorithm provides a principled way to generalize parametric smooth curves to Riemannian manifolds, where straight-line averages are replaced by geodesic interpolation. These manifold-valued Bézier curves have found applications in nonlinear data analysis, including geometric morphometrics and longitudinal data analysis in medicine, archaeology, and meteorology<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>.

## History

Paul de Faget de Casteljau developed the algorithm at Citroën; his 1963 notes show it applied to a cubic curve with poles \( A, B, C, D \), using barycentric coordinates \( \lambda, \mu \) for the parameter domain<sup>[2](https://www.researchgate.net/profile/James-Peters-3/post/Since_the_Bernstein_basis_is_more_stable_than_the_1_x_x2_x3_basis_why_do_we_use_the_second_one/attachment/59d62e4cc49f478072e9ef35/AS%3A273573887840257%401442236505726/download/Farouki-on-Berstein-basis-2012.pdf)</sup>. He and Pierre Étienne Bézier, who worked on the UNISURF CAD system at Renault, almost simultaneously but independently searched for mathematical tools to construct and manipulate complex shapes with the then-novel digital computers<sup>[1](https://www.sciencedirect.com/science/article/pii/S0167839624000220)</sup>. Within twenty years of its invention, de Casteljau's algorithms had become a fundamental tool in CAGD, applied in car and ship design, the aircraft industry, and medical and geological representations<sup>[16](https://www.sciencedirect.com/science/article/pii/S0167839699000230)</sup>.

## References

1. [Martin Hanik, Esfandiar Nava-Yazdani, Christoph von Tycowicz (2024). De Casteljau's algorithm in geometric data analysis: Theory and application. Computer Aided Geometric Design 110.](https://www.sciencedirect.com/science/article/pii/S0167839624000220)
2. [Rida T. Farouki (2012). The Bernstein polynomial basis: a centennial retrospective.](https://www.researchgate.net/profile/James-Peters-3/post/Since_the_Bernstein_basis_is_more_stable_than_the_1_x_x2_x3_basis_why_do_we_use_the_second_one/attachment/59d62e4cc49f478072e9ef35/AS%3A273573887840257%401442236505726/download/Farouki-on-Berstein-basis-2012.pdf)
3. [CS 418: Bézier curves, University of Illinois (2022).](https://courses.physics.illinois.edu/cs418/fa2022/text/bezier.html)
4. [Márton Valasek (2025). Register-Efficient Linear-Time Evaluation in the Bernstein Basis. Computer Graphics Forum.](https://onlinelibrary.wiley.com/doi/10.1111/cgf.70403)
5. [Geometric Modelling lecture notes (rational Bézier curves), University of Miskolc.](https://citeseerx.ist.psu.edu/document?doi=fca198bee49c67521579e7d9aea4da2b13dc6d62&repid=rep1&type=pdf)
6. [Samuel Buss. 3D Computer Graphics: A Mathematical Introduction with OpenGL, 2nd edition draft.](https://mathweb.ucsd.edu/~sbuss/MathCG2/SecondEdDraft.pdf)
7. [CSCI 480/580 Lab: Spline Curves, Western Washington University.](https://facultyweb.cs.wwu.edu/~wehrwes/courses/csci480_21w/spline_lab/)
8. [CS 284 Lecture 3: CAGD Splines, UC Berkeley (1998).](https://people.eecs.berkeley.edu/~sequin/CS284/LEC98/L3.htm)
9. [Fast and Exact Continuous Collision Detection with Bernstein Sign Classification.](https://pmc.ncbi.nlm.nih.gov/articles/PMC4283478/)
10. [Fast subdivision of Bézier curves. arXiv:2509.15691.](https://arxiv.org/abs/2509.15691)
11. [Compensated de Casteljau algorithm in K times the working precision. arXiv:1808.10387.](https://arxiv.org/abs/1808.10387)
12. [On the accuracy of de Casteljau-type algorithms and Bernstein representations. Computer Aided Geometric Design 106 (2023).](https://www.sciencedirect.com/science/article/pii/S0167839623000754)
13. [Fast evaluation of derivatives of Bézier curves. Computer Aided Geometric Design (2024).](https://www.sciencedirect.com/science/article/abs/pii/S0167839624000116)
14. [Evaluation of the derivative of a polynomial in Bernstein form. Journal of Computational and Applied Mathematics.](https://www.sciencedirect.com/science/article/abs/pii/S0096300304004795)
15. [Chapter 4: B-Spline Curves, course notes, Universidad Politécnica de Madrid.](https://dcain.etsin.upm.es/~leonardo/etema4.htm)
16. [Wolfgang Boehm (1999). On de Casteljau's algorithm. Computer Aided Geometric Design 16(7), 587–605.](https://www.sciencedirect.com/science/article/pii/S0167839699000230)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Analysis and mathematical models › Numerical analysis and computation*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license