Abstract
Corner cutting algorithms are used in different fields and, in particular, play a relevant role in Computer Aided Geometric Design. Evaluation algorithms such as the de Casteljau algorithm for polynomials and the de Boor–Cox algorithm for B‐splines are examples of corner cutting algorithms. Here backward and forward error analysis of corner cutting algorithms are performed. The running error is also analyzed and as a consequence the general algorithm is modified to include the computation of an error bound.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Aumann, Corner cutting curves and a new characterization of Bézier and B-spline curves, Computer-Aided Geom. Design 14 (1997) 449–474.
J.M. Carnicer and J.M. Peña, Shape preserving representations and optimality of the Bernstein basis, Adv. Comput. Math. 1 (1993) 173–196.
J.M. Carnicer and J.M. Peña, Total positivity and optimal bases, in: Total Positivity and its Applications, eds. M. Gasca and C.A. Micchelli (Kluwer Academic, Dordrecht, 1996) pp. 133–155.
G. Farin, Curves and Surfaces for Computer Aided Geometric Design (Academic Press, San Diego, 1988).
R.T. Farouki and T.N.T. Goodman, On the optimal stability of Bernstein basis, Math. Comp. 65 (1996) 1553–1566.
R.T. Farouki and V.T. Rajan, On the numerical condition of polynomials in Bernstein form, Computer-Aided Geom. Design 4 (1987) 191–216.
M. Gasca and J.M. Peña, Corner cutting algorithms and totally positive matrices, in: Curves and Surfaces in Geometric Design, eds. P.J. Laurent, A. Le Méhauté and L.L. Schumaker (A.K. Peters, Wellesley, 1994) pp. 177–184.
M. Gasca and J.M. Peña, On factorizations of totally positive matrices, in: Total Positivity and its Applications, eds. M. Gasca and C.A. Micchelli (Kluwer Academic, Dordrecht, 1996) pp. 109–130.
T.N.T. Goodman, Shape preserving representations, in: Mathematical Methods in CAGD, eds. T. Lyche and L.L. Schumaker (Academic Press, Boston, 1989) pp. 333–357.
T.N.T. Goodman and C.A. Micchelli, Corner cutting algorithms for the Bézier representation of free form curves, Linear Algebra Appl. 99 (1988) 225–252.
T.N.T. Goodman and H.B. Said, Shape preserving properties of the generalized Ball basis, Computer-Aided Geom. Design 8 (1991) 115–121.
N.J. Higham, Accuracy and Stability of Numerical Algorithms (SIAM, Philadelphia, PA, 1996).
F.W.J. Olver, Error bounds for polynomial evaluation and complex arithmetic, IMA J. Numer. Anal. 2 (1982) 377–406.
J.M. Peña, Shape preserving representations for trigonometric polynomial curves, Computer-Aided Geom. Desing 14 (1997) 5–11.
J.M. Peña, B-splines and optimal stability, Math. Comp. 66 (1997) 1555–1560.
G.W. Stewart, Error analysis of the algorithm for shifting the zeros of a polynomial by synthetic division, Math. Comp. 25 (1971) 135–139.
N.K. Tsao, Error analysis of splitting algorithms for polynomials, Numer. Math. 32 (1979) 409–421.
J.H. Wilkinson, The evaluation of the zeros of ill-conditioned polynomials, Parts I and II, Numer. Math. 1 (1959) 150–166 and 167–180.
J.H. Wilkinson, Rounding Errors in Algebraic Processes, Notes on Applied Science, Vol. 32 (Her Majesty's Stationery Office, London, 1963).
H. Wozniakowski, Rounding error analysis for the evaluation of a polynomial and some of its derivatives, SIAM J. Numer. Anal. 11 (1974) 780–787.
Rights and permissions
About this article
Cite this article
Mainar, E., Peña, J. Error analysis of corner cutting algorithms. Numerical Algorithms 22, 41–52 (1999). https://doi.org/10.1023/A:1019190220312
Issue Date:
DOI: https://doi.org/10.1023/A:1019190220312