Fast and Efficient Algorithms for Evaluating Uniform and Nonuniform Lagrange and Newton Curves

Newton-Lagrange Interpolations are widely used in
numerical analysis. However, it requires a quadratic computational
time for their constructions. In computer aided geometric design
(CAGD), there are some polynomial curves: Wang-Ball, DP and
Dejdumrong curves, which have linear time complexity algorithms.
Thus, the computational time for Newton-Lagrange Interpolations
can be reduced by applying the algorithms of Wang-Ball, DP and
Dejdumrong curves. In order to use Wang-Ball, DP and Dejdumrong
algorithms, first, it is necessary to convert Newton-Lagrange
polynomials into Wang-Ball, DP or Dejdumrong polynomials. In
this work, the algorithms for converting from both uniform and
non-uniform Newton-Lagrange polynomials into Wang-Ball, DP and
Dejdumrong polynomials are investigated. Thus, the computational
time for representing Newton-Lagrange polynomials can be reduced
into linear complexity. In addition, the other utilizations of using
CAGD curves to modify the Newton-Lagrange curves can be taken.




References:
[1] I. Newton, Philosophiae Naturalis Principia Mathematica. London,
1687.
[2] I. Newton, Letter to Oldenburg (24 october 1676). in The
Correspondence of Isaac Newton, vol. 2, pp.110-161, 1960.
[3] G. Farin, Curves and Surfaces for Computer Aided Geometric Design,
5th ed. Academic Press, Morgan Kaufman Publishers, San Francisco,
2002.
[4] H. B. Said, Generalized Ball Curve and Its Recursive Algorithm. ACM
Transactions on Graphics, vol. 8, pp. 360-371, 1989.
[5] G. J. Wang, Ball Curve of High Degree and Its Geometric Properties.
Appl. Math.: A Journal of Chinese Universities, vol. 2, pp. 126-140, 1987.
[6] J. Delgado and J. M. Pe˜na, A Shape Preserving Representation with an
Evaluation Algorithm of Linear Complexity. Computer Aided Geometric
Design, vol. 20(1), pp. 1-20, 2008.
[7] W. Hongyi, Unifying Representation of B´ezier Curve And Genaralized
Ball Curves. Appl. Math. J. Chinese Univ. Ser. B, vol. 5(1), pp. 109-121,
2000.
[8] Y. Dan and C. Xinmeng, Another Type Of Generalized Ball Curves And
Surfaces. Acta Mathematica Scientia, vol. 27B(4), pp. 897-907, 2007.
[9] N. Dejdumrong, Efficient Algorithms for Non-rational and Rational
B´ezier Curves. Fifth International Conference on Computer Graphics,
Imaging and Visualisation, 2008.