×

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

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\).

MSC:

52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
PDF BibTeX XML Cite
Full Text: EuDML EMIS