# On-line Algorithms for q-adic Covering of the Unit Interval and for
Covering a Cube by Cubes

###
Marek Lassak

Institut für Informatik

Freie Universität Berlin

Takustr. 9, D-14195 Berlin

email: lassak@inf.fu-berlin.de

Report B 00-04

February 2000

**Abstract**

We present efficient algorithms for the on-line *q*-adic covering of
the unit interval by sequences of segments. The basic method guarantees the
covering provided the total length of segments in a sequence is at least
1+2 · 1/q-1/q^{3}. Other algorithms improve this estimate
for q >= 6. The unit *d*-dimensional cube can only be on-line covered
by arbitrary sequence of cubes of the total volume at least 2^{d} + 5/3 + 5/3 · 2^{-d}.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-00-04.ps.gz