Revisiting the problem of zeros of univariate scalar Béziers

• A fast algorithm for computing roots of univariate scalar Béziers is proposed.
• A speed-up of about an order-of-magnitude is gained compared to previous methods.
• The proposed algorithm has the ability to count multiplicities of roots.

This paper proposes a fast algorithm for computing the real roots of univariate polynomials given in the Bernstein basis. Traditionally, the polynomial is subdivided until a root can be isolated. In contrast, herein we aim to find a root only to subdivide the polynomial at the root. This subdivision based algorithm exploits the property that the Bézier curves interpolate the end-points of their control polygons. Upon subdivision at the root, both resulting curves contain the root at one of their end-points, and hence contain a vanishing coefficient that is factored out. The algorithm then recurses on the new sub-curves, now of lower degree, yielding a computational efficiency. In addition, the proposed algorithm has the ability to efficiently count the multiplicities of the roots. Comparison of running times against the state-of-the-art on thousands of polynomials shows an improvement of about an order-of-magnitude.