On-Line Potato-Sack Algorithm Efficient for Packing Into Small Boxes

The aim of this paper is to show an on-line algorithm for packing sequences of d-dimensional boxes of edge lengths at most 1 in a box of edge lengths at least 1. It is more efficient than a previously known algorithm in the case when packing into a box with short edges. In particular, our method permits packing every sequence of boxes of edge lengths at most 1 and of total volume at most in the unit cube. For packing sequences of convex bodies of diameters at most 1 the result is d! times smaller.     

On-Line Packing Sequences of Cubes in the Unit Cube

Almost thirty years ago Meir and Moser proved that every sequence of d -dimensional cubes of total volume 2 ^)d can be packed in the unit cube. We show that if d 5, then this property holds true also for the on-line packing.     

Approximation of Convex Bodies by Centrally Symmetric Bodies

We present an analog of the well-known theorem of F. John about the ellipsoid of maximal volume contained in a convex body. Let C be a convex body and let D be a centrally symmetric convex body in the Euclidean d-space. We prove that if D is an affine image of D of maximal possible volume contained in C, then C a subset of the homothetic copy of D with the ratio 2d-1 and the homothety center in the center of D. The ratio 2d-1 cannot be lessened as a simple example shows.     

An on-line potato-sack theorem

We discuss packings of sequences of convex bodies of Euclideann-spaceE ⁿ in a box and particularly in a cube. Following an Auerbach-Banach-Mazur-Ulam problem from the well-knownScottish Book, results of this kind are called potato-sack theorems. We consider on-line packing methods which work under the restriction that during the packing process we are given each succeeding “potato” only when the preceding one has been packed. One of our on-line methods enables us to pack into the cube of sided>1 inE ⁿ every sequence of convex bodies of diameters at most 1 whose total volume does not exceed ( ). Asymptotically, asd→∞, this volume is as good as that given by the non-on-line methods previously known. This research was done during the academic year 1987/88, while the first author was visiting the City College of the City University of New York. The second author was supported in part by Office of Naval Research Grant N00014-85-K-0147.     

Approximation of convex bodies by axially symmetric bodies

Let be an arbitrary planar convex body. We prove that contains an axially symmetric convex body of area at least . Also approximation by some specific axially symmetric bodies is considered. In particular, we can inscribe a rhombus of area at least in , and we can circumscribe a homothetic rhombus of area at most about . The homothety ratio is at most . Those factors and , as well as the ratio , cannot be improved.

     

Reduced convex bodies in the plane

A convex bodyR of Euclideand-spaceE ^d is called reduced if there is no convex body properly contained inR of thickness equal to the thickness Δ(R) ofR. The paper presents basic properties of reduced bodies inE ². Particularly, it is shown that the diameter of a reduced bodyR?E ² is not greater than √2Δ(R), and that the perimeter is at most (2+½π)Δ(R). Both the estimates are the best possible.