On the numerical condition of BernsteinBézier subdivision processes
Authors:
R. T. Farouki and C. A. Neff
Journal:
Math. Comp. 55 (1990), 637647
MSC:
Primary 65D10; Secondary 65D15, 68T10, 68U05
MathSciNet review:
1035933
Fulltext 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 ruleofthumb in assessing how far Bézier curves and surfaces may be subdivided without exceeding prescribed (worstcase) bounds on the typical errors in their control points. The exponential growth of with n also argues forcefully against the use of highdegree forms in computeraided geometric design applications.
 [1]
E. Cohen, T. Lyche, and R. Riesenfeld, Discrete Bsplines and subdivision techniques in computeraided geometric design and computer graphics, Comput. Graphics Image Processing 14 (1980), 87111.
 [2]
Mischa
Cotlar and Roberto
Cignoli, An introduction to functional analysis, NorthHolland
Publishing Co., AmsterdamLondon; American Elsevier Publishing Co., Inc.,
New York, 1974. Translated from the Spanish by A. Torchinsky and A.
González Villalobos; NorthHolland Texts in Advanced Mathematics. MR 0405049
(53 #8845)
 [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
(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),
no. 3, 191–216. MR 917780
(89a:65028), http://dx.doi.org/10.1016/01678396(87)900124
 [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 (89c:65033), http://dx.doi.org/10.1016/01678396(88)900167
 [7]
William
Feller, An Introduction to Probability Theory and Its Applications.
Vol. I, John Wiley & Sons, Inc., New York, N.Y., 1950. MR 0038583
(12,424a)
 [8]
R. N. Goldman, Markov chains and computeraided geometric design: Part Iproblems and constraints, ACM Trans. Graphics 3 (1984), 204222.
 [9]
, Markov chains and computeraided geometric design: Part IIexamples and subdivision matrices, ACM Trans. Graphics 4 (1985), 1240.
 [10]
Peter
Henrici, Elements of numerical analysis, John Wiley &
Sons, Inc., New YorkLondonSydney, 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), 3546.
 [12]
Jeffrey
M. Lane and R.
F. Riesenfeld, Bounds on a polynomial, BIT 21
(1981), no. 1, 112–117. MR 616705
(83g:65049), http://dx.doi.org/10.1007/BF01934076
 [13]
I.
J. Schoenberg, On variation diminishing approximation methods,
On numerical approximation. Proceedings of a Symposium, Madison, April
2123, 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
(21 #961)
 [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
(46 #4102)
 [15]
G.
W. Stewart, Introduction to matrix computations, Academic
Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1973. Computer Science and Applied Mathematics. MR 0458818
(56 #17018)
 [16]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [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
(89j:65031)
 [1]
 E. Cohen, T. Lyche, and R. Riesenfeld, Discrete Bsplines and subdivision techniques in computeraided geometric design and computer graphics, Comput. Graphics Image Processing 14 (1980), 87111.
 [2]
 M. Cotlar and R. Cignoli, An introduction to functional analysis, NorthHolland, 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), 191216. MR 917780 (89a:65028)
 [6]
 , Algorithms for polynomials in Bernstein form, Comput. Aided Geom. Design 5 (1988), 126. 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 computeraided geometric design: Part Iproblems and constraints, ACM Trans. Graphics 3 (1984), 204222.
 [9]
 , Markov chains and computeraided geometric design: Part IIexamples and subdivision matrices, ACM Trans. Graphics 4 (1985), 1240.
 [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), 3546.
 [12]
 , Bounds on a polynomial, BIT 21 (1981), 112117. 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, PrenticeHall, Englewood Cliffs, N. J., 1963. MR 0161456 (28:4661)
 [17]
 , The algebraic eigenvalue problem, Oxford Univ. Press, 1988. MR 950175 (89j:65031)
Similar Articles
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:
http://dx.doi.org/10.1090/S00255718199010359330
PII:
S 00255718(1990)10359330
Article copyright:
© Copyright 1990
American Mathematical Society
