De Casteljau's algorithm

In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value.

The algorithm is numerically stable^[1] when compared to direct evaluation of polynomials. The computational complexity of this algorithm is $O(dn^{2})$ , where d is the number of dimensions, and n is the number of control points. There exist faster alternatives.^[2]^[3]

^ Delgado, J.; Mainar, E.; Peña, J. M. (2023-10-01). "On the accuracy of de Casteljau-type algorithms and Bernstein representations". Computer Aided Geometric Design. 106: 102243. doi:10.1016/j.cagd.2023.102243. ISSN 0167-8396.
^ Woźny, Paweł; Chudy, Filip (2020-01-01). "Linear-time geometric algorithm for evaluating Bézier curves". Computer-Aided Design. 118: 102760. arXiv:1803.06843. doi:10.1016/j.cad.2019.102760. ISSN 0010-4485.
^ Fuda, Chiara; Ramanantoanina, Andriamahenina; Hormann, Kai (2024). "A comprehensive comparison of algorithms for evaluating rational Bézier curves". Dolomites Research Notes on Approximation. 17 (9/2024): 56–78. doi:10.14658/PUPJ-DRNA-2024-3-9. ISSN 2035-6803.

[1] Delgado, J.; Mainar, E.; Peña, J. M. (2023-10-01). "On the accuracy of de Casteljau-type algorithms and Bernstein representations". Computer Aided Geometric Design. 106: 102243. doi:10.1016/j.cagd.2023.102243. ISSN 0167-8396.

[2] Woźny, Paweł; Chudy, Filip (2020-01-01). "Linear-time geometric algorithm for evaluating Bézier curves". Computer-Aided Design. 118: 102760. arXiv:1803.06843. doi:10.1016/j.cad.2019.102760. ISSN 0010-4485.

[3] Fuda, Chiara; Ramanantoanina, Andriamahenina; Hormann, Kai (2024). "A comprehensive comparison of algorithms for evaluating rational Bézier curves". Dolomites Research Notes on Approximation. 17 (9/2024): 56–78. doi:10.14658/PUPJ-DRNA-2024-3-9. ISSN 2035-6803.

[1]

[2]

[3]