Günter Rote:

1. The convergence rate of the Sandwich algorithm for approximating convex functions

Computing 48 (1992), 337–361, (Zbl 787.65006). doi:10.1007/BF02238642


The Sandwich algorithm approximates a convex function of one variable over an interval by evaluating the function and its derivative at a sequence of points. The connection of the obtained points is a piecewise linear upper approximation, and the tangents yield a piecewise linear lower approximation. Similarly, a planar convex figure can be approximated by convex polygons.

Different versions of the Sandwich algorithm use different rules for selecting the next evaluation point. We consider four natural rules (interval bisection, slope bisection, maximum error rule, and chord rule) and show that the global approximation error with n evaluation points decreases by the order of O(1/n2), which is optimal.

By special examples we show that the actual performance of the four rules can be very different from each other, and we report computational experiments which compare the performance of the rules for particular functions.

Note: A different proof of the Sandwich algorithm for the two bisection rules is given in the paper Sandwich approximation of univariate convex functions with an application to separable convex programming by Rainer E. Burkard, Horst W. Hamacher, and Günter Rote.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzippedfree PDF view@Springer

2. The convergence rate of the Sandwich algorithm for approximating convex figures in the plane (extended abstract)

In: Proceedings of the Second Canadian Conference on Computational Geometry, Ottawa, August 6–10, 1990. Editor: J. Urrutia; pp. 287–290.


This short paper applies the methods of the first paper to approximating plane figures.

other papers about this subject
Last update: August 27, 2003.