On-line algorithms for the \(q\)-adic covering of the unit interval and for covering a cube by cubes (Q1856599)

An algorithm for the on-line \(q\)-adic covering of the unit interval by sequences of segments is presented. This algorithm guarantees covering provided the total length of segments is at least \(1+\frac{2}{q}-\frac{1}{q^3}\). Next a more sophisticated algorithm is proposed which lowers the above estimate to \(1+\frac{5}{3}\cdot\frac{1}{q}+\frac{5}{3}\cdot\frac{1}{q^2}\). As a consequence, every sequence of cubes of sides at most 1 in \(E^d\) whose total volume is at least \(2^d+\frac{5}{3} + \frac{5}{3}\cdot 2^{-d}\) permits an on-line covering of the unit cube in \(E^d\).