Fast subdivision of Bézier curves

It is well-known that a d-dimensional polynomial Bézier curve of degree n can be subdivided into two segments using the famous de Casteljau algorithm in O(dn²) time. Can this problem be solved more efficiently? In this paper, we show that it is possible to do this in O(dnlogn) time using the fast Fourier transform and its inverse. Experiments show that the direct application of the new method performs well only for small values of n, as the algorithm is numerically unstable. However, a slightly modified version -- which still has O(dnlogn) computational complexity -- offers good numerical quality, which is confirmed by numerical experiments conducted in Python. Moreover, the new method has a nice property: if a Bézier curve is extended by an additional control point, the subdivision can be updated in $O(d)$ time. A similar idea can be applied to speed up the subdivision of rational Bézier curves and rectangular Bézier surfaces, as well as to compute the derivatives of Bézier curves more efficiently.