Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)


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
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 $ P(t)$ on a given interval [a, b] into those on any subinterval $ [\bar a,\bar b]$ is specified by a stochastic matrix which depends only on the degree n of $ P(t)$ and the size and location of $ [\bar a,\bar b]$ relative to [a, b]. We show that in the $ {\left\Vert \bullet \right\Vert _\infty }$-norm, the condition number of M has the simple form $ {\kappa _\infty }({\mathbf{M}}) = {[2f\max ({u_{\bar m}},{v_{\bar m}})]^n}$, where $ {u_{\bar m}} = (\bar m - a)/(b - a)$ and $ {v_{\bar m}} = (b - \bar m)/(b - a)$ are the barycentric coordinates of the subinterval midpoint $ \bar m = \frac{1}{2}( {\bar a + \bar b} )$, and f denotes the "zoom" factor $ (b - a)/(\bar b - \bar a)$ 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 $ {\kappa _\infty }({\mathbf{M}})$ with n also argues forcefully against the use of high-degree forms in computer-aided geometric design applications.

References [Enhancements On Off] (What's this?)

  • [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 (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),
  • [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),
  • [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 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 (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] Jeffrey M. Lane and R. F. Riesenfeld, Bounds on a polynomial, BIT 21 (1981), no. 1, 112–117. MR 616705 (83g:65049),
  • [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 (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 York-London, 1973. Computer Science and Applied Mathematics. MR 0458818 (56 #17018)
  • [16] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, 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)

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

PII: S 0025-5718(1990)1035933-0
Article copyright: © Copyright 1990 American Mathematical Society