The root-finding problem has wide applications in geometric processing and computer graphics. Previous rational cubic clipping methods are either of convergence rate 7/k with O(n2) complexity, or of ...convergence rate 5/k with linear complexity, where n and k are degree of the given polynomial and the multiplicity of the root, respectively. This paper presents an improved rational cubic clipping of linear complexity, which can achieve convergence rate 7/k, or a better one 7/(k−1) for a multiple root such that k ≥ 2. Numerical examples illustrate both efficiency and convergence rate of the new method.
Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of polynomial equations. Among various clipping methods, the ones based on the ...Bernstein–Bézier form have good numerical stability. One of such clipping methods is the k-clipping method, where k=2,3 and often called a cubic clipping method when k=3. It utilizes O(n2) time to find two polynomials of degree k bounding the given polynomial f(t) of degree n, and achieves a convergence rate of k+1 for a single root. The roots of the bounding polynomials of degree k are then used for bounding the roots of f(t). This paper presents a rational cubic clipping method for finding two bounding cubics within O(n) time, which can achieve a higher convergence rate 5 than that of 4 of the previous cubic clipping method. When the bounding cubics are obtained, the remaining operations are the same as those of previous cubic clipping method. Numerical examples show the efficiency and the convergence rate of the new method.
Many problems in computer aided geometric design and computer graphics can be turned into a root-finding problem of a polynomial equation. Among various solutions, clipping methods based on the ...Bernstein–Bézier form usually have good numerical stability. A traditional clipping method using polynomials of degree r can achieve a convergence rate of r+1 for a single root. It utilizes two polynomials of degree r to bound the given polynomial f(t) of degree n, where r=2,3, and the roots of the bounding polynomials are used for clipping off the subintervals containing no roots of f(t). This paper presents a rational cubic clipping method for finding the roots of a polynomial f(t) within an interval. The bounding rational cubics can achieve an approximation order of 7 and the corresponding convergence rate for finding a single root is also 7. In addition, differently from the traditional cubic clipping method solving the two bounding polynomials in O(n2), the new method directly constructs the two rational cubics in O(n) which can be used for bounding f(t) in many cases. Some examples are provided to show the efficiency, the approximation effect and the convergence rate of the new method.
•Use two rational cubics as bounding polynomials.•Achieve a convergence rate 7 for a single root.•It can achieve linear computational complexity O(n) for improved cases.
This paper presents a new approach, called cubic clipping, for computing all the roots of a given polynomial within an interval. In every iterative computation step, two cubic polynomials are ...generated to enclose the graph of the polynomial within the interval of interest. A sequence of intervals is then obtained by intersecting the sequence of strips with the abscissa axis. The sequence of these intervals converges to the corresponding root with the convergence rate 4 for the single roots, 2 for the double roots and super-linear
4
3
for the triple roots. Numerical examples show that cubic clipping has many expected advantages over Bézier clipping and quadratic clipping. We also extend our approach by enclosing the graph of the polynomial using two lower degree
k
<
n
polynomials by degree reduction. The sequence of intervals converges to the corresponding root of multiplicity
s with convergence rate
k
+
1
s
.
