1. The convergence rate of the Sandwich algorithm for approximating
Computing 48 (1992), 337–361, (Zbl 787.65006).
The Sandwich algorithm approximates a convex function of one variable
an interval by evaluating the function and its derivative at a sequence
points. The connection of the obtained points is a piecewise linear
approximation, and the tangents yield a piecewise linear lower
Similarly, a planar convex figure can be approximated by convex
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
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
experiments which compare the performance of the rules for particular
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.
2. The convergence rate of the Sandwich algorithm for approximating
figures in the plane (extended abstract)
In: Proceedings of the Second Canadian Conference on Computational
Geometry, Ottawa, August 6–10, 1990. Editor: J. Urrutia;
This short paper applies the methods of the first paper to
approximating plane figures.
Last update: August 27, 2003.