Fast multidimensional Bernstein-Lagrange algorithms

• Autorzy: Kapusta J. , Smarzewski R.

Identyfikatory

DOI

10.17951/ai.2012.12.2.7-18

• Języki publikacji: EN

Abstrakty

EN

In this paper we present two fast algorithms for the Bézier curves and surfaces of an arbitrary dimension. The first algorithm evaluates the Bernstein-Bézier curves and surfaces at a set of specific points by using the fast Bernstein-Lagrange transformation. The second algorithm is an inversion of the first one. Both algorithms reduce the initial problem to computation of some discrete Fourier transformations in the case of geometrical subdivisions of the d-dimensional cube. Their orders of computational complexity are proportional to those of corresponding d-dimensional FFT-algorithm, i.e. to O (N logN) + O (dN), where N denotes the order of the Bernstein-Bézier curves.

Słowa kluczowe

EN

Bernstein-Lagrange algorithms; Bézier curves; Fourier transformation

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 2
• Strony: 7--18
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Kapusta J.

• Institute of Mathematics and Computer Science, The John Paul II Catholic University of Lublin, ul. Konstantynow 1H, 20-708 Lublin, Poland

autor

Smarzewski R.

• Institute of Mathematics and Computer Science, The John Paul II Catholic University of Lublin, ul. Konstantynow 1H, 20-708 Lublin, Poland

Bibliografia

• 1] Stoer J., Bulirsch R., Introduction to Numerical Analysis, Springer - Verlag, New York 1993.
• [2] Kapusta J., Smarzewski R., Fast algorithms for multivariate interpolation and evaluation at special points, Journal of Complexity 25 (2009): 332.
• [3] Farouki R., Rajan V. T., Algorithms for polynomials in Bernstein form, Computer Aided Geometric Design 5 (1988): 1.
• [4] Mainara E., Pe¨na J. M., Evaluation algorithms for multivariate polynomials in Bernstein-Bézier form, Journal of Approximation Theory 143 (1) (2006): 44.
• [5] Peters J., Evaluation and approximate evaluation of the multivariate Bernstein-Bézier form on a regularly partitioned simplex, ACM Transactions on Mathematical Software 20(4) (1994): 460.
• [6] Phien H. N., Dejdumrong N., Efficient algorithms for Bé zier curves, Computer Aided Geometric Design 17 (2000): 247.
• [7] Aho A., Hopcroft J., Ullman J., The design and analysis of computer algorithms, Addison-Wesley, London 1974.
• [8] Smarzewski R., Kapusta J., Fast Lagrange-Newton transformations, Journal of Complexity 23 (2007): 336.
• [9] Bini D., Pan V. Y., Polynomial and matrix computations: fundamental algorithms, Birkhäuser Verlag, 1994.
• [10] Aho A., Steiglitz K., Ullman J., Evaluating polynomials at fixed sets of points, SIAM Journal Comput. 4 (1975): 533.
• [11] Borwein J. M., Borwein P. B., Pi and the AGM: A study in analytic number theory and computational complexity, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley and Sons, New York, Chichester, Brisbane, Toronto, Singapore, 1987.
• [12] Kapusta J., An efficient algorithm for multivariate Maclaurin-Newton transformation, Annales UMCS Informatica AI VIII (2) (2008): 5.
• [13] Andrews G. E., The theory of partitions (Encyclopedia of mathematics and its applications), Addison-Wesley Publishing Company, 1976.