On-line covering of the unit cube by boxes and by convex bodies

• Autorzy: Januszewski J. , Lassak M.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a method of q-adic on-line covering of the unit d-dimensional cube I[sup]d by arbitrary sequence of boxes of side lengths of the form q[sup]-k for k [is an element of {O, l, 2,...} whose total volume is a number of the order of magnitude 2[sup]d. We also show that every sequence of boxes of side lengths at most 1 and of the total volume at least 4[sup]d. 2.566 ... permits an on-line covering of I[sup]d. Moreover, we estimate the total volume of sequences of convex bodies of diameters at most l which permit an on-line covering of I .

Słowa kluczowe

EN

on-line covering; box; convex body

PL

pokrycie bezpośrednie; bryła wypukła

• Wydawca: Instytut Matematyczny PAN
• Czasopismo: Bulletin of the Polish Academy of Sciences. Mathematics
• Rocznik: 2003
• Tom: Vol. 51, no 3
• Strony: 309--317
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Januszewski J.

• Institute of Mathematics and Physics, ATR, Kaliskiego 7, 85-796 Bydgoszcz

autor

Lassak M.

• Poznań University of Management and Banking, Robocza 4, 61-583 Poznań, Poland

Bibliografia

• [1] H. Groemer, Covering and packing properties of bounded sequences of convex sets, Mathematika, 29 (1982) 18-31.
• [2] H. Groemer, Covering and packing by sequences of convex sets, in: Discrete Geometry and Convexity, Ann. New York Acad. Sci., 440 (1985) 262-278.
• [3] J. Januszewski, M. Lassak, On-line covering by boxes and by convex bodies, Bull. Pol. Ac.: Math., 42 (1994) 69-76.
• [4] J. Januszewski, M. Lassak, G. Rote, G. Woeginger, On-line q-adic covering by the method of the nth interval and its application to on-line covering by cubes, Beiträge Algebra Geom., 37 (1996) 51-65.
• [5] J. Januszewski, M. Lassak, On-line covering of the unit square by boxes, Monogr. Textbooks Pure Appl. Math., 253 (2003) 359-366.
• [6] W. Kuperberg, On-line covering a cube by a sequence of cubes, Discrete Comput. Geom., 42 (1994) 83-90.
• [7] W. Kuperberg, Problem 74: Ein Intervalüberdeckungsspiel, Math. Semesterber., 41 (1994) 207-210.
• [8] M. Lassak, Estimation of the volume of parallelotopes contained in convex bodies, Bull. Pol. Ac.: Math., 41 (1993) 219-223.
• [9] M. Lassak, A survey of algorithms for on-line packing and covering by sequences of convex bodies, Bolyai Soc. Math. Stud., 6 (1997) 129-157.
• [10] M. Lassak, On-line algorithms for q-adic covering of the unit interval and for the covering a cube by cubes, Beiträge Algebra Geom., 43 (2) (2002) 537-549.
• [11] J. W. Moon, L. Moser, Some packing and covering theorems, Colloq. Math., 17 (1967) 103-110.