A planar quadratic clipping method for computing a root of a polynomial in an interval
Xiao-Diao Chen, Weiyin Ma
In Computers & Graphics, 46(0), 2015.
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.
Keyword(s): Optimal approximation order,Root finding,Quadratic clipping,Convergence rate
Article URL: http://dx.doi.org/10.1016/j.cag.2014.09.014
BibTeX format:
@article{Chen:2015:APQ,
  author = {Xiao-Diao Chen and Weiyin Ma},
  title = {A planar quadratic clipping method for computing a root of a polynomial in an interval},
  journal = {Computers & Graphics},
  volume = {46},
  number = {0},
  pages = {89--98},
  year = {2015},
}
Search for more articles by Xiao-Diao Chen.
Search for more articles by Weiyin Ma.

Return to the search page.


graphbib: Powered by "bibsql" and "SQLite3."