Abstract
T. Rado conjectured in 1928 that if ℱ is a finite set of axis-parallel squares in the plane, then there exists an independent subset ℐ⊆ℱ of pairwise disjoint squares, such that ℐ covers at least 1/4 of the area covered by ℱ. He also showed that the greedy algorithm (repeatedly choose the largest square disjoint from those previously selected) finds an independent set of area at least 1/9 of the area covered by ℱ. The analogous question for other shapes and many similar problems have been considered by R. Rado in his three papers (in Proc. Lond. Math. Soc. 51:232–264, 1949; 53:243–267, 1951; and J. Lond. Math. Soc. 42:127–130, 1968) on this subject. After 45 years, Ajtai (in Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys. 21:61–63, 1973) came up with a surprising example disproving T. Rado’s conjecture. We revisit Rado’s problem and present improved upper and lower bounds for squares, disks, convex bodies, centrally symmetric convex bodies, and others, as well as algorithmic solutions to these variants of the problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ajtai, M.: The solution of a problem of T. Rado. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys. 21, 61–63 (1973)
Bereg, S., Dumitrescu, A., Jiang, M.: Maximum area independent set in disk intersection graphs, Int. J. Comput. Geom. Appl., to appear
Braß, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)
Chan, T.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178–189 (2003)
Croft, H.T., Falconer, K.J., Guy, R.K.: Unsolved Problems in Geometry. Springer, New York (1991)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302–1323 (2005)
Fáry, I.: Sur la densité des réseaux de domaines convexes. Bull. Soc. Math. France 78, 252–161 (1950)
Fejes Tóth, L.: Some packing and covering theorems. Acta Sci. Math. (Szeged) 12 A, 62–67 (1950)
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133–137 (1981)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985)
Norlander, G.: A covering problem. Nordisk Mat. Tidskr. 6, 29–31 (1958)
Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)
Preparata, F., Shamos, M.: Computational Geometry, An Introduction. Springer, New York (1985)
Rado, T.: Sur un problème relatif à un théorème de Vitali. Fund. Math. 11, 228–229 (1928)
Rado, R.: Some covering theorems (I). Proc. Lond. Math. Soc. 51, 232–264 (1949)
Rado, R.: Some covering theorems (II). Proc. Lond. Math. Soc. 53, 243–267 (1951)
Rado, R.: Some covering theorems (III). J. Lond. Math. Soc. 42, 127–130 (1968)
Reinhardt, K.: Über die dichteste gitterförmige Lagerung kongruenter Bereiche in der Ebene und eine besondere Art konvexer Kurven. Abh. Math. Sem. Hamburg 10, 216–230 (1934)
Sokolin, A.: Concerning a problem of Rado. C. R. Acad. Sci. URSS (N.S.) 26, 871–872 (1940)
Tammela, P.: An estimate of the critical determinant of a two-dimensional convex symmetric domain. Izv. Vyss. Ucebn. Zaved. Mat. 12, 103–107 (1970) (in Russian)
Yaglom, I.M., Boltyanskiĭ, V.G.: Convex Figures. Holt, Rinehart and Winston, New York (1961)
Zalgaller, V.A.: Remarks on a problem of Rado. Matem. Prosveskcheric 5, 141–148 (1960)
Zwillinger, D.: CRC Standard Mathematical Tables and Formulae, 31st edn. CRC Press, Boca Raton (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188.
M. Jiang was partially supported by NSF grant DBI-0743670.
Rights and permissions
About this article
Cite this article
Bereg, S., Dumitrescu, A. & Jiang, M. On Covering Problems of Rado. Algorithmica 57, 538–561 (2010). https://doi.org/10.1007/s00453-009-9298-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9298-z