Cover Decomposition Page

maintained by Dömötör Pálvölgyi

WARNING, THIS PAGE IS OBSOLATE!

New homepage for cover decomposition and polychromatic colorings!

Entries contain only best (and not first related) results! For cover decomposition, a number m means that an m fold covering (of a finite point set) decomposes into 2 (resp. k) coverings. In the polychromatic coloring problem we want the smallest number m such that each set with at least m points (of a given finite set) contains all k colors. (For translates, this is equivalent to cover decomposition [P80].) Note that in many papers a set is called cover-decomposable if any (sufficiently many fold) covering of the WHOLE plane with its translates is decomposable into two coverings, so this table is about a slightly different problem, though they are often equivalent.

Cover decomposition Polychromatic coloring of points
of translates intoof homothets intowith respect to homothets
2 coveringsk coveringsk coveringswith k colors
wedge2k--
triangle9 [KP15] lower bound: 5 [KP15]O(k) [GV09]O(k^5.09) [CKMU13,KP15]O(k^4.09) [KP13,KP15]
convex n-gon (n>3)yes [PT10] but no bound of only n;
it has to grow with n [P13]
O(k) [GV09]not [K13] O(k^11.6) for squares (1484 for k=2) [AKV15], open for n>4;
if yes for k=2, then poly(k) for all k [KP13]
bottomless rectangle3 [K11] sharp O(k) [GV09]O(k^5.09) [CKMU13,KP15]
for k=2: 3 [K11]
3k-2 [A+13] lower bound: 1.67k
for k=2: 4 [K11] sharp
octant9 [KP15] lower bound: 5 [KP15]O(k^5.09) [CKMU13,KP15]--
all halfplanes3 [F10] sharp3k-2 [SY10] lower bound: 2k-1-2k-1 [SY10] sharp, same for pseudohalfplanes in [KP14]
all axis parallel strips3 [A+09] sharp2k-1 [A+09] -2k-1 [A+09] lower bound: 3k/2-1


Other results that did not fit to the table:
-If for every k points are polychromatic colorable with k colors for sets of size Ck, then there is an epsilon-net of size C/epsilon.
-Centrally symmetric (open or closed) convex polygons are cover-decomposable over ANY planar set [KT14]. Similar statements for other polygons are OPEN.
-Concave polygons that have special wedges are not cover-decomposable [P10]. In fact polygons are completely classified with respect to our definition [PT10] but if coverings of the whole plane are considered, there are still some unsolved concave polygons [P10].
-Discs (and convex sets that have two parallel tangents which both touch it in a point in whose neighborhood the boundary of curves) are not cover-decomposable [P13]. For balls and homothets this was proved earlier [MP86], [PTT05]. Other sets, e.g., a halfdisc, are still OPEN.
-Halfspaces (even upper halfspaces) are not cover-decomposable, polychromatic coloring is also not possible (stated in [A+08b] as corollary of [PTT05]).
-All lines are not cover-decomposable, polychromatic coloring is also not possible [PTT05].
-Polyhedra in 3 and higher dimensions are not cover-decomposable [P10], from 4-dim not even orthant [CK11].
-All axis-parallel rectangles are not cover-decomposable [PTT05], polychromatic coloring is also not possible [CPST09].
-All strips are not cover-decomposalbe, polychromatic coloring is also not possible [PTT05].


Papers related to cover-decomposition, numbered by the year of their first available version and ordered according to their abbreviation:
[AKV15] E. Ackerman, B. Keszegh, M. Vizer, Coloring points with respect to squares, SoCG 2016, 16 pages [arXiv:1512.01953]
[A10] B. Ács, Síkfedések szétbonthatósága (in Hungarian), Master Thesis, Eötvös University Budapest, 2010 - 19-fold coverings with triangles decompose into 2 coverings.
[A+08] G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, P. Ramos, Decomposition of multiple coverings into more parts, Discrete and Computational Geometry 44:706-723, 2010 [arXiv:0807.0552] - O(k) for centrally symmetric convex sets.
[A+08b] G. Aloupis, J. Cardinal, S. Collette, S. Langerman, S. Smorodinsky, Coloring Geometric Range Spaces, Discrete and Computational Geometry 41:348-362, 2009
[A+09] G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S.Langerman, O. Schwartz, S. Smorodinsky, P. Taslakian, Colorful Strips, Graphs and Combinatorics 27:327-339, 2011 [arXiv:0904.2115] - higher dimensional axis parallel strips are also shown to be cover-decomposable and polychromatic colorable, circular permutations ("looking around" from a point) are also studied.
[A+13] A. Asinowski, J. Cardinal, N. Cohen, S. Collette, T. Hackl, M. Hoffmann, K. Knauer, S. Langerman, M. Lason, P. Micek, G. Rote, T. Ueckerdt, Coloring hypergraphs induced by dynamic point sets and bottomless rectangles, Algorithms and Data Structures, LNCS 8037:73-84, 2013 [arXiv:1302.2426]
[BPRS10] B. Bollobás, D. Pritchard, T. Rothvoss, A. Scott, Cover-Decomposition and Polychromatic Numbers, SIAM J. Discrete Math., 27:240-256, 2013 [arXiv:1009.6144] - question is studied for abstract hypergraphs families.
[CK11] J. Cardinal, M. Korman, Coloring planar homothets and three-dimensional hypergraphs, Comput. Geom. 46:1027-1035, 2013 [arXiv:1101.0565] - studies proper coloring of planar homothets.
[CKMU12] J. Cardinal, K. Knauer, P. Micek, T. Ueckerdt, Making triangles colorful, J. Comput. Geom. 4:240-246, 2013 [arXiv:1212.2346] - O(k^8) polychromatic coloring w/r/t homothets of triangles.
[CKMU13] J. Cardinal, K. Knauer, P. Micek, T. Ueckerdt, Making Octants Colorful and Related Covering Decomposition Problems [arXiv:1307.2705] - apart from main result, also shown that it is not possible to cover-decompose intervals with semi-online algorithm.
[CPST09] X. Chen, J. Pach, M. Szegedy, G. Tardos, Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles, Random Struct. Algorithms, 34:11-23, 2009 [preprint]
[EMS09] M. Elekes, T. Mátrai, L. Soukup, On splitting infinite-fold covers, Fundamenta Mathematicae 212:95-127, 2011 [arXiv:0911.2774] - some results related to infinite cardinalities.
[F10] R. Fulek, Coloring geometric hypergraph defined by an arrangement of half-planes, CCCG, 71-74, 2010 [arXiv:1002.4529]
[GV09] M. Gibson, K. Varadarajan, Decomposing Coverings and the Planar Sensor Cover Problem, Discrete and Computational Geometry, 46:313-333, 2011 [arXiv:0905.1093]
[K11] B. Keszegh, Coloring half-planes and bottomless rectangles, Computational Geometry: Theory and Applications, 45:495-507, 2012 [arXiv:1105.0169]
[K13] I. Kovács, Indecomposable coverings with homothetic polygons, Discrete and Computational Geometry, 53:817-824, 2015 [arXiv:1312.4597]
[KLP12] B. Keszegh, N. Lemons, D. Pálvölgyi, Online and quasi-online colorings of wedges and intervals, SOFSEM, LNCS 7741, 292-306, 2013, to appear in Order [arXiv:1207.4415] - certain online coloring algorithms do not exist and simpler proofs for some results of [K11].
[KP11] B. Keszegh, D. Pálvölgyi, Octants are Cover Decomposable, Discrete and Computational Geometry, 47:598-609, 2012 [arXiv:1101.3773] - 12-fold coverings with octants decompose into 2 coverings.
[KP12] B. Keszegh, D. Pálvölgyi, Octants are cover-decomposable into many coverings, Computational Geometry 47:585-588, 2014 [arXiv:1207.0672] - 12^2^k-fold coverings with octants decompose into k coverings.
[KP13] B. Keszegh, D. Pálvölgyi, Convex Polygons are Self-Coverable, Discrete and Computational 51(4):885-895, 2014 [arXiv:1307.2411]
[KP14] B. Keszegh, D. Pálvölgyi, An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes, WG 2015, 266-280, [arXiv:1410.0258]
[KP15] B. Keszegh, D. Pálvölgyi, More on Decomposing Coverings by Octants, Journal of Computational Geometry 6:300-315, 2015 [arXiv:1503.01669]
[KT14] I. Kovács, G. Tóth, Multiple coverings with closed polygons, Electronic Journal of Combinatorics 22:18 pages, 2015 [arXiv:1403.2653]
[MP86] P. Mani-Levitska, J. Pach, Decomposition problems for multiple coverings with unit balls, manuscript, 1986 [some parts]
[P10] D. Pálvölgyi. Indecomposable coverings with concave polygons, Discrete and Computational Geometry, 44:577-588, 2010 [preprint]
[P13] D. Pálvölgyi, Indecomposable coverings with unit discs [arXiv:1310.6900v1]
[P80] J. Pach, Decomposition of multiple packing and covering, Diskrete Geometrie, 2. Kolloq. Math. Inst. Univ. Salzburg, 1980 [scan.ps]
[P86] J. Pach, Covering the plane with convex polygons, Discrete and Computational Geometry 1:73-81, 1986 - centrally symmetric convex sets are cover-decomposable.
[PP13] J. Pach, D. Pálvölgyi, Unsplittable coverings in the plane, Advances in Mathematics 302:433-457, 2016 [arXiv:1310.6900]
- merger of [MP86] and [P13] and more.
[PPT14] J. Pach, D. Pálvölgyi, G. Tóth, Survey on Decomposition of Multiple Coverings, in Geometry, Intuitive, Discrete, and Convex (I. Bárány, K. J. Böröczky, G. Fejes Tóth, J. Pach eds.), Bolyai Society Mathematical Studies 24:219-257, Springer-Verlag, 2014 [preprint] - survey of results and methods.
[PT09] J. Pach, G. Tóth, Decomposition of multiple coverings into many parts, Computational Geometry: Theory and Applications 42:127-133, 2009 [preprint] - O(k^2) for centrally symmetric convex sets.
[PT10] D. Pálvölgyi, G. Tóth, Convex polygons are cover-decomposable, Discrete and Computational Geometry, 43:483-496, 2010 [preprint]
[PTT05] J. Pach, G. Tardos, G. Tóth, Indecomposable coverings, Canadian Mathematical Bulletin, 52:451-463, 2009 [preprint]
[SY10] S. Smorodinsky, Y. Yuditsky, Polychromatic Coloring for Half-Planes, J. Comb. Theory, Ser. A 119:146-154, 2012 [arXiv:1006.3191]
[TT07] G. Tardos, G. Tóth, Multiple coverings of the plane with triangles, Discrete and Computational Geometry 38:443-450, 2007 [preprint] - 43-fold coverings with triangles decompose into 2 coverings.