Survey of Real Root Finding of Univariate Polynomial Equation in CAGD/CG

Many basic algorithms in the field of CAGD/CC can be reduced to the problems of root finding of univariate polynomials.In the early years of CAGD/CG,this problem is solved by converting to power basis for root finding,since many algorithms in power basis have been widely used.However,root finding algorithms for polynomials in Bernstein form are getting more and more attractive for their numerical stability and intuitive geometric significance.In this survey,different root finding algorithms for univariate polynomial in both power and Bernstein forms are introduced,analyzed and compared in terms of theoretical basis,numerical robustness and computational efficiency.Meanwhile,suggestions on how to select suitable algorithm are given.