Efficient rational quadratic clipping method for computing roots of a polynomial

The root-finding problem is one of key issues for visualizing implicit curves and surfaces, and has wide applications in computer-aided design, computer graphics and geometric computing for image and video. This paper presents a rational quadratic clipping method for computing a simple root of a polynomial f(t) of degree n within an interval, which preserves the optimal computation stability of the Bernstein-Bezier representation. Different from previous clipping methods based on interpolation, it optimizes the selection of the inner point, which can achieve the convergence rate 12 by using rational quadratic polynomials. Difference from previous clipping methods by computing bounding polynomials, it provides a simple method of linear complexity to directly bound the root; at the same time, it needs to compute the roots of quadratic polynomials and avoids solving cubic equations, and leads to a higher computational efficiency. In principle, it also works well for a non-polynomial case. Numerical examples show higher convergence rate and better computation efficiency of the new method.