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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

7 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)89-98
Journal / PublicationComputers and Graphics (Pergamon)
Publication statusPublished - Feb 2015


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

Research Area(s)

  • Convergence rate, Optimal approximation order, Quadratic clipping, Root finding