Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, and Emo Welzl:

Approximation of convex figures by pairs of rectangles

  1. (Preliminary extended abstract)
    In: Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS'90), Rouen, February 1990. Lecture Notes in Computer Science 415, Springer-Verlag, 1990, pp. 240–249, (Zbl 729.68087, MR #91e:68148). doi:10.1007/3-540-52282-4_47
  2. (Improved and extended version)
    Computational Geometry, Theory and Applications 10 (1998), pp. 77–87. doi:10.1016/S0925-7721(96)00019-3


We consider the problem of approximating a convex figure in the plane by a pair (r,R) of homothetic (i. e., similar and parallel) rectangles with r contained in C and R containing C. We show the existence of such pairs where the sides of the outer rectangle have length at most double the length of the inner rectangle, thereby solving a problem posed by Pólya and Szegö. If the n vertices of a convex polygon C are given as a sorted array, such an approximating pair of rectangles can be computed in time O(log2n).
  PostScript file (gzippedpdf file (gzipped)
other papers about this subject