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] 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)

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

American Mathematical Society