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

Authors: Taweechai Nuntawisuttiwong, Natasha Dejdumrong

Abstract:

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.

Keywords: Newton interpolation, Lagrange interpolation, linear complexity.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.3455677

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.