A planar quadratic clipping method for computing a root of a polynomial in an interval. (February 2015)

• Record Type: Journal Article
• Authors: Chen, Xiao-Diao; Ma, Weiyin
• Is Part Of: Computers & graphics. Volume 46(2015)
• Page Start: 89
• Page End: 98
• Publication Date: 2015-02
• Subjects: Optimal approximation order -- Root finding -- Quadratic clipping -- Convergence rate; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2014.09.014
• Languages: English
• ISSNs: 0097-8493

Abstract

Abstract: 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 R 1 space, it derives three quadratic curves in R 2 space for approximating ( t, f ( t ) ) instead, which leads to a higher approximation order. Two bounding polynomials are then computed in O ( n 2 ) 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 R 1 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. Abstract : Graphical abstract: Abstract : Highlights: A planar quadratic clipping method is presented by using R 2 space instead. Achieve a convergence rate of 4 by using quadratic polynomials. Obtain a linear computation complexity O ( n ) instead of O ( n 2 ) for a convex case. In principle, the idea can be directly extended to the planar cubic clipping method.