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 Free Access

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]**M. Cotlar and R. Cignoli,*An introduction to functional analysis*, North-Holland, Amsterdam, 1974. MR**0405049 (53:8845)****[3]**P. de Casteljau,*Courbes et surfaces à pôles*, André Citroën Automobiles SA, Paris (unpublished notes), 1963.**[4]**G. Farin,*Curves and surfaces for computer aided geometric design*, Academic Press, New York, 1988. MR**974109 (90c:65014)****[5]**R. T. Farouki and V. T. Rajan,*On the numerical condition of polynomials in Bernstein form*, Comput. Aided Geom. Design**4**(1987), 191-216. MR**917780 (89a:65028)****[6]**-,*Algorithms for polynomials in Bernstein form*, Comput. Aided Geom. Design**5**(1988), 1-26. MR**945302 (89c:65033)****[7]**W. Feller,*An introduction to probability theory and its applications*. Vol. I, Wiley, New York, 1950. MR**0038583 (12:424a)****[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]**P. Henrici,*Elements of numerical analysis*, Wiley, New York, 1964. MR**0166900 (29:4173)****[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]**-,*Bounds on a polynomial*, BIT**21**(1981), 112-117. MR**616705 (83g:65049)****[13]**I. J. Schoenberg,*On variation diminishing approximation methods*, On Numerical Approximation (R. E. Langer, ed.), Univ. of Wisconsin Press, Madison, WI, 1959. MR**0102167 (21:961)****[14]**E. M. Stein and G. L. Weiss,*Introduction to Fourier analysis on Euclidean spaces*, Princeton Univ. Press, Princeton, N.J., 1971. MR**0304972 (46:4102)****[15]**G. W. Stewart,*Introduction to matrix computations*, Academic Press, New York, 1973. MR**0458818 (56:17018)****[16]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Englewood Cliffs, N. J., 1963. MR**0161456 (28:4661)****[17]**-,*The algebraic eigenvalue problem*, Oxford Univ. Press, 1988. MR**950175 (89j:65031)**

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