Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

An algorithm for covering a given region by a sequence of convex bodies $\{C_i\}$ is an {\it on-line} method if the sets $C_i$ are given one at a time, and $C_{i+1}$ is revealed only after $C_i$ has been put in place. We solve a problem of Lassak [1991] concerning on-line covering the unit cube by a sequence of (smaller) cubes, by proving that in in $n$-dimensional Euclidean space every sequence of cubes whose total volume is greater than $4^n$ admits an on-line covering of the unit cube. Without the ``on-line'' restriction, the best possible volume bound is known to be $2^n-1$, obtained by Groemer [1982] and, independently, by the Bezdek brothers [1984]. The presented algorithm makes use of a suitable cube-filling (Peano) curve, and the volume bound is obtained by an estimate of the curve's efficiency. A closer look at the efficiency allows to improve the volume bound by lowering it to slightly under $3^n$. The problem of maximum efficiency cube-filling curve as well as its finite, combinatorial version remain open.