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

Lassak, Marek

Beitr. Algebra Geom. 43, No. 2, 537-549 (2002).

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

Reviewer: Elena E.Berdysheva (Stuttgart)

MSC:

52C17

Packing and covering in \(n\) dimensions (aspects of discrete geometry)

Keywords:

on-line covering; \(q\)-adic covering; sequence of segments; sequence of cubes