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
Abstract
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.
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.
Abstract
This short paper applies the methods of the first paper to
approximating plane figures.
Last update: August 27, 2003.