Filip Chudy

Filip Chudy, Paweł Woźny

A new algorithm for computing a point on a polynomial or rational curve in Bézier form is proposed. The method has a geometric interpretation and uses only convex combinations of control points. The new algorithm's computational complexity is linear with respect to the number of control points and its memory complexity is $O(1)$. Some remarks on similar methods for surfaces in rectangular and triangular Bézier form are also given.

Filip Chudy, Paweł Woźny

New differential-recurrence properties of dual Bernstein polynomials are given which follow from relations between dual Bernstein and orthogonal Hahn and Jacobi polynomials. Using these results, a fourth-order differential equation satisfied by dual Bernstein polynomials has been constructed. Also, a fourth-order recurrence relation for these polynomials has been obtained; this result may be useful in the efficient solution of some computational problems.

Paweł Woźny, Filip Chudy

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^2)$ time. Can this problem be solved more efficiently? In this paper, we show that it is possible to do this in $O(dn\log{n})$ 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(dn\log{n})$ computational complexity -- offers good numerical quality, which is confirmed by numerical experiments conducted in \textsf{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.

Filip Chudy, Paweł Woźny

We present new representations of Gauss--Legendre polynomials and their derivatives in the shifted power basis and in bases related to symmetric orthogonal Jacobi polynomials. Using these representations and certain recurrence relations, we propose efficient $O(n^2+dn)$ methods for evaluating a Gauss--Legendre curve of degree $n$ in $\mathbb E^d$. We also propose algorithms for multipoint evaluation with computational complexity $O(Mdn+dn^2)$, where $M$ is the number of evaluation points.