A planar quadratic clipping method for computing a root of a polynomial in an interval

This paper presents a new quadratic clipping method for computing a root of a polynomial f(t) of degree n within an interval. Different from the traditional one in ℝ¹ space, it derives three quadratic curves in ℝ² space for approximating (t,f(t)) instead, which leads to a higher approximation order. Two bounding polynomials are then computed in O(n²) for bounding the roots of f(t) within the interval. The new clipping method achieves a convergence rate of 4 for a single root, compared with that of 3 from traditional method using quadratic polynomial approximation in ℝ¹ space. When f(t) is convex within the interval, the two bounding polynomials are able to be directly constructed without error estimation, which leads to computational complexity O(n). Numerical examples show the approximation effect and efficiency of the new method. The method is particularly useful for the fly computation in many geometry processing and graphics rendering applications.