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 , where d is the number of dimensions, and n is the number of control points. There exist faster alternatives.[2][3]

  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.