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

• A planar quadratic clipping method is presented by using R2R2 space instead.
• Achieve a convergence rate of 4 by using quadratic polynomials.
• Obtain a linear computation complexity O(n  ) instead of O(n2)O(n2) for a convex case.
• In principle, the idea can be directly extended to the planar cubic clipping method.

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 R1R1 space, it derives three quadratic curves in R2R2 space for approximating (t,f(t))(t,f(t)) instead, which leads to a higher approximation order. Two bounding polynomials are then computed in O(n2)O(n2) 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 R1R1 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.

Figure optionsDownload high-quality image (207 K)Download as PowerPoint slide