Commenced in January 2007
Paper Count: 30855
Fast and Efficient Algorithms for Evaluating Uniform and Nonuniform Lagrange and Newton Curves
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.3455677Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 174
 I. Newton, Philosophiae Naturalis Principia Mathematica. London, 1687.
 I. Newton, Letter to Oldenburg (24 october 1676). in The Correspondence of Isaac Newton, vol. 2, pp.110-161, 1960.
 G. Farin, Curves and Surfaces for Computer Aided Geometric Design, 5th ed. Academic Press, Morgan Kaufman Publishers, San Francisco, 2002.
 H. B. Said, Generalized Ball Curve and Its Recursive Algorithm. ACM Transactions on Graphics, vol. 8, pp. 360-371, 1989.
 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.
 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.
 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.
 Y. Dan and C. Xinmeng, Another Type Of Generalized Ball Curves And Surfaces. Acta Mathematica Scientia, vol. 27B(4), pp. 897-907, 2007.
 N. Dejdumrong, Efficient Algorithms for Non-rational and Rational B´ezier Curves. Fifth International Conference on Computer Graphics, Imaging and Visualisation, 2008.