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³. 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