## 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)
Full Text: