Remote Access Mathematics of Computation
Green Open Access

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
  • [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,
  • [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,
  • [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,
  • [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

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

Article copyright: © Copyright 1990 American Mathematical Society