On the numerical condition of Bernstein-Bézier subdivision processes

Authors:
R. T. Farouki and C. A. Neff

Journal:
Math. Comp. **55** (1990), 637-647

MSC:
Primary 65D10; Secondary 65D15, 68T10, 68U05

DOI:
https://doi.org/10.1090/S0025-5718-1990-1035933-0

MathSciNet review:
1035933

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The linear map **M** that takes the Bernstein coefficients of a polynomial on a given interval [*a, b*] into those on any subinterval is specified by a stochastic matrix which depends only on the degree *n* of and the size and location of relative to [*a, b*]. We show that in the -norm, the condition number of **M** has the simple form , where and are the barycentric coordinates of the subinterval midpoint , and *f* denotes the "zoom" factor of the subdivision map. This suggests a practical rule-of-thumb in assessing how far Bézier curves and surfaces may be subdivided without exceeding prescribed (worst-case) bounds on the typical errors in their control points. The exponential growth of with *n* also argues forcefully against the use of high-degree forms in computer-aided geometric design applications.

**[1]**E. Cohen, T. Lyche, and R. Riesenfeld,*Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics*, Comput. Graphics Image Processing**14**(1980), 87-111.**[2]**Mischa Cotlar and Roberto Cignoli,*An introduction to functional analysis*, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1974. Translated from the Spanish by A. Torchinsky and A. González Villalobos; North-Holland Texts in Advanced Mathematics. MR**0405049****[3]**P. de Casteljau,*Courbes et surfaces à pôles*, André Citroën Automobiles SA, Paris (unpublished notes), 1963.**[4]**Gerald Farin,*Curves and surfaces for computer aided geometric design*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. A practical guide; With contributions by P. Bézier and W. Boehm. MR**974109****[5]**R. T. Farouki and V. T. Rajan,*On the numerical condition of polynomials in Bernstein form*, Comput. Aided Geom. Design**4**(1987), no. 3, 191–216. MR**917780**, https://doi.org/10.1016/0167-8396(87)90012-4**[6]**R. T. Farouki and V. T. Rajan,*Algorithms for polynomials in Bernstein form*, Comput. Aided Geom. Design**5**(1988), no. 1, 1–26. MR**945302**, https://doi.org/10.1016/0167-8396(88)90016-7**[7]**William Feller,*An Introduction to Probability Theory and Its Applications. Vol. I*, John Wiley & Sons, Inc., New York, N.Y., 1950. MR**0038583****[8]**R. N. Goldman,*Markov chains and computer-aided geometric design*:*Part*I--*problems and constraints*, ACM Trans. Graphics**3**(1984), 204-222.**[9]**-,*Markov chains and computer-aided geometric design*:*Part*II--*examples and subdivision matrices*, ACM Trans. Graphics**4**(1985), 12-40.**[10]**Peter Henrici,*Elements of numerical analysis*, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR**0166900****[11]**J. M. Lane and R. F. Riesenfeld,*A theoretical development for the computer generation and display of piecewise polynomial surfaces*, IEEE Trans. Pattern Anal. Mach. Intell.**2**(1980), 35-46.**[12]**Jeffrey M. Lane and R. F. Riesenfeld,*Bounds on a polynomial*, BIT**21**(1981), no. 1, 112–117. MR**616705**, https://doi.org/10.1007/BF01934076**[13]**I. J. Schoenberg,*On variation diminishing approximation methods*, On numerical approximation. Proceedings of a Symposium, Madison, April 21-23, 1958, Edited by R. E. Langer. Publication no. 1 of the Mathematics Research Center, U.S. Army, the University of Wisconsin, The University of Wisconsin Press, Madison, 1959, pp. 249–274. MR**0102167****[14]**Elias M. Stein and Guido Weiss,*Introduction to Fourier analysis on Euclidean spaces*, Princeton University Press, Princeton, N.J., 1971. Princeton Mathematical Series, No. 32. MR**0304972****[15]**G. W. Stewart,*Introduction to matrix computations*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR**0458818****[16]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456****[17]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Monographs on Numerical Analysis, The Clarendon Press, Oxford University Press, New York, 1988. Oxford Science Publications. MR**950175**

Retrieve articles in *Mathematics of Computation*
with MSC:
65D10,
65D15,
68T10,
68U05

Retrieve articles in all journals with MSC: 65D10, 65D15, 68T10, 68U05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1990-1035933-0

Article copyright:
© Copyright 1990
American Mathematical Society