×

Unsplittable coverings in the plane. (English) Zbl 1350.52007

Summary: A system of sets forms an \(m\)-fold covering of a set \(X\) if every point of \(X\) belongs to at least \(m\) of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density estimates for sphere packings as well as by the planar sensor cover problem. It has been the prevailing conjecture for 35 years (settled in many special cases) that for every plane convex body \(C\), there exists a constant \(m = m(C)\) such that every \(m\)-fold covering of the plane with translates of \(C\) splits into 2 coverings. In the present paper, it is proved that this conjecture is false for the unit disk. The proof can be generalized to construct, for every \(m\), an unsplittable \(m\)-fold covering of the plane with translates of any open convex body \(C\) which has a smooth boundary with everywhere positive curvature. Somewhat surprisingly, unbounded open convex sets \(C\) do not misbehave, they satisfy the conjecture: every 3-fold covering of any region of the plane by translates of such a set \(C\) splits into two coverings. To establish this result, we prove a general coloring theorem for hypergraphs of a special type: shift-chains. We also show that there is a constant \(c > 0\) such that, for any positive integer \(m\), every \(m\)-fold covering of a region with unit disks splits into two coverings, provided that every point is covered by at most \(c 2^{m / 2}\) sets.

MSC:

52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., A non-linear lower bound for planar epsilon-nets, Discrete Comput. Geom., 47, 2, 235-244 (2012) · Zbl 1232.68161
[2] Alon, N.; Spencer, J. H., The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization (2008), Wiley: Wiley Hoboken, NJ
[3] Aloupis, G.; Cardinal, J.; Collette, S.; Langerman, S.; Orden, D.; Ramos, P., Decomposition of multiple coverings into more parts, Discrete Comput. Geom., 44, 3, 706-723 (2010) · Zbl 1206.52013
[4] Asinowski, A.; Cardinal, J.; Cohen, N.; Collette, S.; Hackl, T.; Hoffmann, M.; Knauer, K.; Langerman, S.; Lason, M.; Micek, P.; Rote, G.; Ueckerdt, T., Coloring hypergraphs induced by dynamic point sets and bottomless rectangles, (Algorithms and Data Structures. Algorithms and Data Structures, Lecture Notes in Comput. Sci., vol. 8037 (2013), Springer: Springer Heidelberg), 73-84 · Zbl 1391.68104
[5] Bollobás, B.; Pritchard, D.; Rothvoß, T.; Scott, A., Cover-decomposition and polychromatic numbers, SIAM J. Discrete Math., 27, 1, 240-256 (2013) · Zbl 1268.05061
[6] Buchsbaum, A. L.; Efrat, A.; Jain, S.; Venkatasubramanian, S.; Yi, K., Restricted strip covering and the sensor cover problem, (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 (2007), ACM: ACM New York), 1056-1063 · Zbl 1302.68278
[7] Cardinal, J.; Knauer, K.; Micek, P.; Ueckerdt, T., Making triangles colorful, J. Comput. Geom., 4, 1, 240-246 (2013) · Zbl 1422.52007
[8] Cardinal, J.; Knauer, K.; Micek, P.; Ueckerdt, T., Making octants colorful and related covering decomposition problems, SIAM J. Discrete Math., 28, 4, 1948-1959 (2014) · Zbl 1309.05068
[9] Erdős, P., On a combinatorial problem, Nord. Mat. Tidskr., 11, 5-10 (1963), 40 · Zbl 0116.01104
[10] Erdős, P.; Lovász, L., Problems and results on 3-chromatic hypergraphs and some related questions, (Infinite and Finite Sets, vol. II. Infinite and Finite Sets, vol. II, Colloq., Keszthely, 1973. Infinite and Finite Sets, vol. II. Infinite and Finite Sets, vol. II, Colloq., Keszthely, 1973, Colloq. Math. Soc. János Bolyai, vol. 10 (1975), North-Holland: North-Holland Amsterdam), 609-627, dedicated to P. Erdős on his 60th birthday
[11] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · Zbl 0012.27010
[12] Even, G.; Lotker, Z.; Ron, D.; Smorodinsky, S., Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM J. Comput., 33, 1, 94-136 (2003) · Zbl 1069.68120
[13] Feige, U.; Halldórsson, M. M.; Kortsarz, G., Approximating the domatic number, SIAM J. Comput., 32, 1, 172-195 (2002/2003) · Zbl 1021.05072
[14] Fejes Tóth, G., New results in the theory of packing and covering, (Convexity and Its Applications (1983), Birkhäuser: Birkhäuser Basel), 318-359
[15] Fejes Tóth, G.; Kuperberg, W., A survey of recent results in the theory of packing and covering, (New Trends in Discrete and Computational Geometry. New Trends in Discrete and Computational Geometry, Algorithms Combin., vol. 10 (1993), Springer: Springer Berlin), 251-279 · Zbl 0798.52020
[17] Gebauer, H., Disproof of the neighborhood conjecture with implications to SAT, Combinatorica, 32, 5, 573-587 (2012) · Zbl 1289.68047
[18] Gibson, M.; Varadarajan, K., Optimally decomposing coverings with translates of a convex polygon, Discrete Comput. Geom., 46, 2, 313-333 (2011) · Zbl 1229.52019
[19] Grünbaum, B., Venn diagrams and independent families of sets, Math. Mag., 48, 12-23 (1975) · Zbl 0305.05004
[20] Haussler, D.; Welzl, E., \(ϵ\)-Nets and simplex range queries, Discrete Comput. Geom., 2, 2, 127-151 (1987) · Zbl 0619.68056
[21] Keszegh, B.; Pálvölgyi, D., Octants are cover-decomposable, Discrete Comput. Geom., 47, 3, 598-609 (2012) · Zbl 1237.52013
[22] Keszegh, B.; Pálvölgyi, D., Octants are cover-decomposable into many coverings, Comput. Geom., 47, 5, 585-588 (2014) · Zbl 1285.05061
[23] Keszegh, B.; Pálvölgyi, D., Convex polygons are self-coverable, Discrete Comput. Geom., 51, 4, 885-895 (2014) · Zbl 1302.52002
[24] Keszegh, B.; Pálvölgyi, D., An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes · Zbl 1417.05069
[25] Kovács, I., Indecomposable coverings with homothetic polygons · Zbl 1320.52020
[26] Mani-Levitska, P.; Pach, J., Decomposition problems for multiple coverings with unit balls, manuscript, 1986. Parts of the manuscript are available at
[27] Matoušek, J., The determinant bound for discrepancy is almost tight, Proc. Amer. Math. Soc., 141, 2, 451-460 (2013) · Zbl 1259.05179
[28] Miller, E. W., On a property of families of sets, C. R. Soc. Sci. Varsovie, 30, 31-38 (1937) · JFM 63.0832.01
[29] Naszódi, M.; Taschuk, S., On the transversal number and VC-dimension of families of positive homothets of a convex body, Discrete Math., 310, 1, 77-82 (2010) · Zbl 1192.52006
[30] Pach, J., Decomposition of multiple packing and covering, (Diskrete Geometrie, 2. Kolloq.. Diskrete Geometrie, 2. Kolloq., Math. Inst. Univ. Salzburg (1980)), 169-178
[31] Pach, J., Covering the plane with convex polygons, Discrete Comput. Geom., 1, 1, 73-81 (1986) · Zbl 0595.52015
[32] Pach, J.; Pálvölgyi, D.; Tóth, G., Survey on decomposition of multiple coverings, (Geometry—Intuitive, Discrete, and Convex. Geometry—Intuitive, Discrete, and Convex, Bolyai Soc. Math. Stud., vol. 24 (2013), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 219-257 · Zbl 1319.52024
[33] Pach, J.; Tardos, G.; Tóth, G., Indecomposable coverings, Canad. Math. Bull., 52, 3, 451-463 (2009) · Zbl 1245.52008
[34] Pach, J.; Tóth, G., Decomposition of multiple coverings into many parts, Comput. Geom., 42, 2, 127-133 (2009) · Zbl 1156.05013
[35] Pálvölgyi, D., Decomposition of geometric set systems and graphs (2010), EPFL: EPFL Lausanne, PhD thesis
[36] Pálvölgyi, D., Indecomposable coverings with concave polygons, Discrete Comput. Geom., 44, 3, 577-588 (2010) · Zbl 1211.52017
[37] Pálvölgyi, D.; Tóth, G., Convex polygons are cover-decomposable, Discrete Comput. Geom., 43, 3, 483-496 (2010) · Zbl 1194.52017
[38] Radhakrishnan, J.; Srinivasan, A., Improved bounds and algorithms for hypergraph 2-coloring, Random Structures Algorithms, 16, 1, 4-32 (2000) · Zbl 0942.05024
[39] Tardos, G.; Tóth, G., Multiple coverings of the plane with triangles, Discrete Comput. Geom., 38, 2, 443-450 (2007) · Zbl 1135.52007
[40] Varadarajan, K., Weighted geometric set cover via quasi-uniform sampling, (STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing (2010), ACM: ACM New York), 641-647 · Zbl 1293.68300
[41] Winkler, P., Puzzled: covering the plane, Commun. ACM, 52, 11, 112 (2009), See also:
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.