Toggle info:

Show only:

Show also:

Layout:

**\({\cal H}^R({\cal B},{\cal F})\)**: given families of regions \(\cal B\) and \(\cal F\), and relation \(R\), \({\cal H}^R({\cal B},{\cal F})\) is
the hypergraph with a vertex \(v_b\) for each \(B\) in \(\cal B\) and a hyperedge \(h_F\) for each region \(F\) in \(\cal F\) where \(h_F\) contains
those vertices \(v_B\) for which \(B ~R~ F\) (\(B\) is in relation \(R\) with \(F\)). In \({\cal H}^R({\cal B},{\cal F})\) we get rid of multiple copies
of hyperedges, so it is a simple hypergraph.

We refer to \({\cal H}^R({\cal B},{\cal F})\) simply as '\(B ~R~ F\)', so, e.g., for the hypergraph whose
vertices are a finite number of points in the plane and whose edges are defined by a finite number of disks with the containment relation, we refer to
as 'pt/disk'.

Possible relations \(R\) are:

**- intersection relation, denoted by '/'**: \(B\) intersects \(F\);

when \({\cal H}^/({\cal B},{\cal F})\) and \({\cal H}^/({\cal F},{\cal B})\)
are equivalent, then we refer to both of them by using the relation 'X' (e.g., 'ptXtrans disk' refers to both 'pt/transl disk' and 'transl disk/pt')

**- containment relation, denoted by '\(\subset\)'**: \(B\) contains \(F\)

**- reverse containment relation, denoted by '\(\supset\)'**: \(F\) contains \(B\)

**Axis-parallel** (rectangle, bottomless rectangle, strip) is abbreviated to **a-p**

**Pseudo-disk** family:

Its members are simply connected regions of the plane whose boundaries intersect at most twice.

In most theorems/proofs, the following weaker parity condition is also sufficient: for any two members of the family, \(A\) and \(B\), any path
\(\pi_A\subset A\) connecting any two points \(a_1,a_2\in A\setminus B\) properly crosses any path \(\pi_B\subset B\) connecting any two points
\(b_1,b_2\in B\setminus A\) an even number of times. This holds for non-piercing families as well:

**Non-piercing** family:

For any two members of the family, \(A\) and \(B\), \(A\setminus B\) is connected.

**Stabbed** family:

The intersection of all members is non-empty, e.g., they all contain the origin.

**Dynamic** family:

Given a hypergraph \(\cal H\), its dynamic closure is a hypergraph on the same vertex set that we get by ordering the vertices of \(\cal H\)
in an arbitrary way and then for every hyperedge \(E\) of \(\cal H\) every prefix of \(E\) (with the above order) is a hyperedge in the dynamic closure
of \(\cal H\).

**Proper coloring** of a hypergraph \(\cal H\):

a coloring of the points of \(\cal H\) such that every hyperedge of \(\cal H\) of size at least \(2\) contains \(2\) points with different colors.

**Chromatic number (\(\chi\))** of a hypergraph \(\cal H\):

\(\chi(\cal H)\) denotes the minimum number of colors in a proper coloring of \(\cal H\).

**Chromatic number (\(\chi\))** of \(B\) with respect to \(F\) with relation \(R\):

\(\chi\) denotes the maximum \(\chi(\cal H)\) over every hypergraph \({\cal H}^R({\cal B'},{\cal F'})\) where \(\cal B'\) is a finite subfamily
of \(\cal B\) and \(\cal F'\) is a finite subfamily of \(\cal F\);

\(n\) denotes the size of \(\cal B'\) when \(\chi\) depends on \(n\).

**\({\cal H}_m\) and \({\cal H}_{\ge m}\)**: given a hypergraph \(\cal H\),

\({\cal H}_{=m}\) denotes the subhypergraph of \(\cal H\) containing the hyperedges of size exactly \(m\) and

\({\cal H}_{\ge m}\) (or simply \({\cal H}_{m}\)) denotes the subhypergraph of \(\cal H\) containing the hyperedges of size at least \(m\).

\({\cal H}_{=2}\) is called the ** Delaunay-graph** of \({\cal H}\).

**m-chromatic number (\(\chi_m\))** of \(\cal B\) with respect to \(\cal F\) with relation \(R\):

\(\chi_m\) denotes the smallest number \(c\) for which there exists a constant number \(m\) such that the chromatic number
of \({\cal H}^R_m({\cal B'},{\cal F'})\) is \(\le c\) for every \(\cal B'\) finite subfamily of \(\cal B\) and \(\cal F'\)
finite subfamily of \(\cal F\).

**\(m_2\)**: suppose that \(\chi_m=2\), then

\(m_2\) denotes the smallest number \(m\) such that the chromatic number of \({\cal H}^R_m({\cal B'},{\cal F'})\) is \(\le 2\) for every
\(\cal B'\) finite subfamily of \(\cal B\) and \(\cal F'\) finite subfamily of \(\cal F\).

**Polychromatic \(k\)-coloring** of \(\cal H\):

a \(k\)-coloring of the points of \(\cal H\) such that every hyperedge of \(\cal H\) contains points with all \(k\) colors.

**\(m_k\)**: suppose that \(\chi_m=2\), then

\(m_k\) denotes the smallest number \(m_k\) such that \({\cal H}^R_{m_k}({\cal B'},{\cal F'})\) is polychromatic \(k\)-colorable for every
\(\cal B'\) finite subfamily of \(\cal B\) and \(\cal F'\) finite subfamily of \(\cal F\).

**Number of edges** of a hypergraph in \(\cal H\):

**(\(e\))** of \(\cal B\):

\(e\) denotes the maximal possible number of hyperedges of a hypergraph in \(\cal B\) on \(n\) vertices.

**(\(e_k\))** of \(\cal B\):

\(e_k\) denotes the maximal possible number of \(k\)-uniform hyperedges of a hypergraph in \(\cal B\) on \(n\) vertices.

**(\(e_{\le k}\))** of \(\cal B\):

\(e_{\le k}\) denotes the maximal possible number of hyperedges of size at most \(k\) of a hypergraph in \(\cal B\) on \(n\) vertices.

**(\(a\))** of \(\cal B\):

\(a\) denotes the maximal possible number of hyperedges of a hypergraph in \(\cal B\) on \(n\) vertices which is an antichain, i.e.,
is containment-free.

**VC-dim** of \(\cal H\):

\(\cal H\) shatters \(X\) if for every \(Y\) subset of \(X\) there is a hyperedge \(H\) of \(\cal H\) that intersects \(X\) in exactly \(Y\).

**\(VC\)-dim**: denotes the size of the largest \(X\) that is shattered by \(\cal B\).

**\(C\)-shallow hitting set** of \(\cal H\):

a set of the points of \(X\) is a \(C\)-shallow hitting set of \(\cal H\) if it intersects each set in \(1\) to \(C\) elements.

a family is an antichain if it is containment-free, i.e., no member of it contains another member.

**\(\tau_s\)**: denotes the smallest number for which there is a \(\tau_s\)-shallow hitting set for every antichain \(\cal B'\)
finite subfamily of \(\cal B\).

**\(\varepsilon\)-net** of \(\cal H\):

a subset of the vertices of \(\cal H\) is an \(\varepsilon\)-net of a hypergraph \(\cal H\) on \(n\) vertices if it intersects each set
of size \(\ge\varepsilon n\).

if \(\cal H\) is embedded in some space \(X\), then a weak \(\varepsilon\)-net of a hypergraph \(\cal H\) on \(n\) points can contain
other elements than these \(n\) points (and it intersects each set of size \(\ge\varepsilon n\)).

**\(\varepsilon\)-net** of \(\cal B\):

denotes the maximal size of a minimal \(\varepsilon\)-net for a hypergraph in \(\cal B\).

**weak-\(\varepsilon\)-net** of \(\cal B\):

denotes the maximal size of a minimal weak-\(\varepsilon\)-net for a hypergraph in \(\cal B\).

**Discrepancy** (combinatorial and measure) of a hypergraph (family):

**\(discr\)** of \(\cal B\): denotes the maximum difference in the number of blue and red points in a hyperedge in an optimal two-coloring
of the vertices of a hypergraph on \(n\) vertices from \(\cal B\).

**\(D\)** of \(\cal B\): denotes the maximum difference in the number of points and \(n\) times the measure of a set from \(\cal B\)
intersected by a unit cube for an optimal set of \(n\) points.

Left-click: select item.

Shift or Ctrl + Left-click: add item to selection.

Right-click or long-click: hide item.

: the family has χ=∞.

: the family has χ<∞ and χₘ>2 or it is not known if it has χ=∞ or χₘ=2.

: the family has χₘ=2 and it has mₖ non-linear or it is not known to have linear mₖ.

: the family has χₘ=2 and mₖ=O(k).

[AKP19] E. Ackerman, B. Keszegh, D. Pálvölgyi, Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
[arxiv]

[AKV15] E. Ackerman, B. Keszegh, M. Vizer, Coloring points with respect to squares, SoCG 2016, 16 pages [arXiv]

[AP13] E. Ackerman, R. Pinchasi, On coloring points with respect to rectangles, J. Combinatorial Theory Ser. A. 120:811-815, 2013.

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

[AEGR12] D. Ajwani, K. Elbassioni, S. Govindarajan, S. Ray, Conflict-free coloring for rectangle ranges using O(n^.382) colors, Discrete Comput. Geom. 48:39–52, 2012.

[Ale90] R. Alexander, Geometric methods in the study of irregularities of distribution, Combinatorica 10:115-136, 1990 [doi]

[Alo12] N. Alon. A non-linear lower bound for planar epsilon-nets. Discrete and Computational Geometry, 47(2):235–244, 2012.

[AloBFK92] N. Alon, I. Barany, Z. Furedi and D. J. Kleitman, Point selections and weak epsilon-nets for convex hulls, Comb. Prob. Comput. 1, 189-200, 1992.

[AloDOV03] N. Alon, G. Ding, B. Oporowski, and D. Vertigan, Partitioning into graphs with only small components, J. Combin. Theory Ser. B 87, 231–243, 2003.

[AloG86] N. Alon, E. Györi, The number of small semispaces of a finite set of points in the plane, Journal of Combinatorial Theory Series A 41:154-157, 1986 [doi]

[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] - 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+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] - 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

[ADEP18] Boris Aronov, Anirudh Donakonda, Esther Ezra, Rom Pinchasi, On Pseudo-disk Hypergraphs [arXiv]

[AroES10] Boris Aronov, Esther Ezra, and Micha Sharir, Small-size eps-nets for axis-parallel rectangles and boxes, SIAM J. Comput. 39 (7): 3248-3282, 2010

[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]

[AxeU16] M. Axenovich, T. Ueckerdt, Density of range capturing hypergraphs, JoCG 7, 21 pages, 2016. [JoCG]

[BalS19] J. Balogh, J. Samotij, An efficient container lemma [arXiv] arXiv.

[BalS18] J. Balogh, J. Solymosi, On the number of points in general position in the plane, Discrete Analysis 16, 20 pp, 2018 [arXiv] arXiv.

[Bec81] J. Beck, Balanced two-colorings of finite sets in the square I, Combinatorica (1981) 1: 327–335.

[Bec87] J. Beck, Irregularities of distribution, I. Acta Math. 159 (1987), 1--49.

[Bec88a] J. Beck, Irregularities of distribution. II. Proc. London Math. Soc. (3) 56 (1988), no. 1, 1–50.

[Bec88b] J. Beck, On irregularities of point sets in the unit square, Combinatorics (Eger, 1987), 63–74, Colloq. Math. Soc. Jnos Bolyai, 52, North-Holland, Amsterdam, 1988.

[Bec88c] J. Beck, On the discrepancy of convex plane sets, Monatsh. Math., 105:91–106, 1988.

[Ber72] C. Berge, Balanced matrices, Mathematical Programming 2:19-31, 1972 [doi]

[BBCP19] Ahmad Biniaz, Prosenjit Bose, Jean Cardinal and Michael Payne. Three-Coloring Three-Dimensional Uniform Hypergraphs, CCCG 2019, [preprint]

[BPRS10] B. Bollobás, D. Pritchard, T. Rothvoss, A. Scott, Cover-Decomposition and Polychromatic Numbers, SIAM J. Discrete Math. 27:240-256, 2013 [arXiv] - question is studied for abstract hypergraphs families.

[Bro04] H. Brönnimann, Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane, JCDCG 2004: 54–61.

[BukMN11] B. Bukh, J. Matousek, and G. Nivasch, Lower bounds for weak epsilon-nets and stair-convexity, Israel J. Math. 182, 199–228, 2011 [arXiv].

[BPR13] S. Buzaglo, R. Pinchasi, G. Rote, Topological hypergraphs, Thirty Essays on Geometric Graph Theory, (Ed. J. Pach), 71–81, Springer, New York, 2013 [preprint]

[BHP08] S. Buzaglo, R. Holzman, R. Pinchasi, On s-intersecting curves and related problems, SoCG '08, pages 79–84 [preprint]

[CKMU12] J. Cardinal, K. Knauer, P. Micek, T. Ueckerdt, Making triangles colorful, J. Comput. Geom. 4:240-246, 2013 [arXiv] - 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] - apart from main result, also shown that it is not possible to cover-decompose intervals with semi-online algorithm.

[CK11] J. Cardinal, M. Korman, Coloring planar homothets and three-dimensional hypergraphs, Comput. Geom. 46:1027-1035, 2013 [arXiv] - studies proper coloring of planar homothets.

[C12] T. Chan, Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set, SoCG 2012, 293–302 [preprint]

[ChaGKS12] T. M. Chan, E. Grant, J. Konemann, and M. Sharpe, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, SODA 2012, 1576–1585.

[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]

[CheFSS14] N. Chevallier, A. Fruchard, D. Schmitt, J.-C. Spehner, Separation by convex pseudocircles, SoCG '14, pages 444–453 [HAL]

[Cor35] J. G. van der Corput, Verteilungsfunktionen I and II, Akad. Wetensch. Amsterdam, Proc., 38:813–821 and 1058–1066, 1935.

[Dey98] T. K. Dey, Improved bounds for planar k-sets and related problems, Discrete and Computational Geometry 19: 373–382, 1998 [doi]

[Drm93] M. Drmota, Irregularities of distribution and convex sets, Grazer Math. Ber., 318:9–16, 1993.

[EMS09] M. Elekes, T. Mátrai, L. Soukup, On splitting infinite-fold covers, Fundamenta Mathematicae 212:95-127, 2011 [arXiv] - some results related to infinite cardinalities.

[EspJ14] L. Esperet and G. Joret, Colouring planar graphs with three colours and no large monochromatic components, Combinatorics, Probability and Computing, 23:551–570, 2014.

[F10] R. Fulek, Coloring geometric hypergraph defined by an arrangement of half-planes, CCCG, 71-74, 2010 [arXiv]

[GV09] M. Gibson, K. Varadarajan, Decomposing Coverings and the Planar Sensor Cover Problem, Discrete and Computational Geometry, 46:313-333, 2011 [arXiv]

[HS05] S. Har-Peled, S. Smorodisky, Conflict-free coloring of points and simple regions in the plane, Discrete Comput. Geom. 34:47–70, 2005.

[HauW87] D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete and Computational Geometry, 2:127–151, 1987.

[KS17] C. Keller, S. Smorodinsky, Conflict-free coloring of intersection graphs of geometric objects, [arXiv]

[KelS18] C. Keller, S. Smorodinsky, A new lower bound on Hadwiger-Debrunner numbers in the plane, [arXiv]

[K11] B. Keszegh, Coloring half-planes and bottomless rectangles, Computational Geometry: Theory and Applications, 45:495-507, 2012 [arXiv]

[K17] B. Keszegh, Coloring intersection hypergraphs of pseudo-disks, SoCG 2018, [arXiv]

[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] - certain online coloring algorithms do not exist and simpler proofs for some results of [K11].

[KP13] B. Keszegh, D. Pálvölgyi, Convex Polygons are Self-Coverable, Discrete and Computational 51(4):885-895, 2014 [arXiv]

[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]

[KP15] B. Keszegh, D. Pálvölgyi, More on Decomposing Coverings by Octants, Journal of Computational Geometry 6:300-315, 2015 [arXiv]

[KP11] B. Keszegh, D. Pálvölgyi, Octants are Cover Decomposable, Discrete and Computational Geometry, 47:598-609, 2012 [arXiv] - 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] - 12^2^k-fold coverings with octants decompose into k coverings.

[K13] I. Kovács, Indecomposable coverings with homothetic polygons, Discrete and Computational Geometry, 53:817-824, 2015 [arXiv]

[KP16] B. Keszegh, D. Pálvölgyi, Proper Coloring of Geometric Hypergraphs, SoCG 2017, 1-15, [arXiv]

[K17b] N. Kumar, On the minimum edge size for 2-colorability and realizability of hypergraphs by axis-parallel rectangles, CCCG 2017: 226-231, [proceedings]

[KleMRV97] J. Kleinberg, R. Motwani, P. Raghavan, and S. Venkatasubramanian, Storage management for evolving databases, FOCS 1997, 353–362.

[KomPW92] J. Komlós, J. Pach, and G. J. Woeginger, Almost tight bounds for epsilon-nets, Discrete and Computational Geometry, 7:163–173, 1992.

[KT14] I. Kovács, G. Tóth, Multiple coverings with closed polygons, Electronic Journal of Combinatorics 22:18 pages, 2015 [arXiv]

[Lau08] Sören Laue, Geometric Set Cover and Hitting Sets for Polytopes in R3, STACS 2008: 479-490.

[LiuO18] Chun-Hung Liu, Sang-il Oum, Partitioning H-minor free graphs into three subgraphs with no large components, Journal of Combinatorial Theory B 128:114-133, 2018 [doi]

[Mat91] J. Matoušek, Lower Bounds on the Length of Monotone Paths in Arrangements, J. Discrete Comput Geom 6:129-134 (1991) [doi]

[Mat92] J. Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, 2(3):169–186, 1992.

[Mat95] J. Matoušek, Tight upper bounds for the discrepancy of half-spaces, J. Discrete Comput Geom 13: 593-601, 1995 [doi]

[Mat99] J. Matoušek, On the Discrepancy for Boxes and Polytopes, Monatshefte für Mathematik 127: 325–336, 1999 [doi]

[MatSW90] J. Matoušek, R. Seidel, and E. Welzl, How to net a lot with little: Small epsilon-nets for disks and halfspaces, SoCG 1990, 16–22.

[MatWW93] J. Matoušek, E. Welzl, L. Wernisch, Discrepancy and ε-approximations for bounded VC-dimension, Combinatorica 13 (1993), 455–466.

[MP86] P. Mani-Levitska, J. Pach, Decomposition problems for multiple coverings with unit balls, manuscript, 1986 [some parts] - merged into [PP13].

[MusDG18] N.H. Mustafa, K. Dutta, A. Ghosh, A Simple Proof of Optimal Epsilon Nets, Combinatorica 38: 1269–1277, 2018 [HAL]

[NaszT10] Márton Naszódi, Steven Taschuk, On the transversal number and VC-dimension of families of positive homothets of a convex body, Discrete Mathematics, 310:77-82, 2010 [doi].

[NewNN12] Alantha Newman, Ofer Neiman, and Aleksandar Nikolov, Beck's Three Permutations Conjecture: A Counterexample and Some Consequences, FOCS 2012.

[Nik17] A. Nikolov, Tighter Bounds for the Discrepancy of Boxes and Polytopes, Mathematika, 63(3), 1091-1113, 2017.

[P86] J. Pach, Covering the plane with convex polygons, Discrete and Computational Geometry 1:73-81, 1986 - centrally symmetric convex sets are cover-decomposable.

[P80] J. Pach, Decomposition of multiple packing and covering, Diskrete Geometrie, 2. Kolloq. Math. Inst. Univ. Salzburg, 1980 [scan.ps]

[PP13] J. Pach, D. Pálvölgyi, Unsplittable coverings in the plane, Advances in Mathematics 302:433-457, 2016 [arXiv] - 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.

[PT08] J. Pach, G. Tardos, Coloring axis-parallel rectangles, J. of Combinatorial Theory, Series A, 117(6):776-782, 2010 [journal]

[PT13] J. Pach and G. Tardos, Tight lower bounds for the size of epsilon-nets, Journal of the AMS, 26:645–658, 2013.

[PTT05] J. Pach, G. Tardos, G. Tóth, Indecomposable coverings, Canadian Mathematical Bulletin, 52:451-463, 2009 [preprint]

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

[P13] D. Pálvölgyi, Indecomposable coverings with unit discs [arXiv:1310.6900v1] - merged into [PP13].

[P10] D. Pálvölgyi. Indecomposable coverings with concave polygons, Discrete and Computational Geometry 44:577-588, 2010 [preprint]

[PT10] D. Pálvölgyi, G. Tóth, Convex polygons are cover-decomposable, Discrete and Computational Geometry 43:483-496, 2010 [preprint]

[PV19] D. Pálvölgyi, N. Varadarajan, Colouring bottomless rectangles and arborescences [arXiv:1912.05251]

[PayW13] M. S. Payne, D. R. Wood, On the general position subset selection problem, SIAM J. Discrete Math., 27(4):1727–1733, 2013 [arxiv] - studies max independent for bounded clique in 3-uniform ptXline.

[Pec85] G. W. Peck, On k-sets in the plane, Discrete Mathematics 56:73-74, 1985 [preprint]

[Pin14] R. Pinchasi, A finite family of pseudodiscs must include a "small" pseudodisc, SIAM Journal on Discrete Mathematics 28:1930-1934, 2014 [preprint]

[PinG14] R. Pinchasi, G. Rote, On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs, Israel Journal of Mathematics 172:337-348, 2009 [doi]

[PyrR08] E. Pyrga and S. Ray, New existence proofs for ε-nets, SoCG 2008, 199–207.

[RamR18] R. Raman, S. Ray, Planar Support for Non-piercing Regions and Applications, ESA 2018, 14 pages. [DROPS] - planar support for non-piercing regions.

[Rot54] K. F. Roth, On irregularities of distribution, Mathematika, 1:73–79, 1954.

[Rot80] K. F. Roth, On irregularities of distribution IV. Ada Arith., 37: 67-75, 1980.

[Rub19] N. Rubin, An improved bound for weak epsilon-nets in the plane, FOCS 2018 [arxiv]

[Sch72] W. M. Schmidt. On irregularities of distribution VII. Acta Arith., 21:45–50, 1972.

[Sch75] W. M. Schmidt. On irregularities of distribution IX. Acta Arith., 27:385–396, 1975.

[Sha91] M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom., 6(4):593-613, 1991 [doi]

[ShaST01] M. Sharir, S. Smorodinsky, G. Tardos, An improved bound for k-sets in three dimensions, Discrete Comput. Geom., 26(2):195–204, 2001 [doi]

[Skr98] Skriganov, Ergodic theory on SL(n), diophantine approximations and anomalies in the lattice point problem, Invent math 132:1–72, 1998 [doi]

[S07] S. Smorodinsky, On the chromatic number of geometric hypergraphs, SIAM Journal on Discrete Mathematics 21(3):676-687, 2007 [journal]

[SY10] S. Smorodinsky, Y. Yuditsky, Polychromatic Coloring for Half-Planes, J. Comb. Theory, Ser. A 119:146-154, 2012 [arXiv]

[Spe85] J. Spencer, Six standard deviations suffice, Transactions of the American Mathematical Society, 289(2):679–706, 1985.

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

[T01] G. Tóth, Point sets with many k-sets, Discrete and Computational Geometry 26:187-194, 2001.

[Var10] K. R. Varadarajan, Weighted geometric set cover via quasi-uniform sampling, STOC 2010, 641–648.

[W65] G. Wegner, 0ber eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner, Israel J. of Math 3: 187-198, 1965.

[AKV15] E. Ackerman, B. Keszegh, M. Vizer, Coloring points with respect to squares, SoCG 2016, 16 pages [arXiv]

[AP13] E. Ackerman, R. Pinchasi, On coloring points with respect to rectangles, J. Combinatorial Theory Ser. A. 120:811-815, 2013.

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

[AEGR12] D. Ajwani, K. Elbassioni, S. Govindarajan, S. Ray, Conflict-free coloring for rectangle ranges using O(n^.382) colors, Discrete Comput. Geom. 48:39–52, 2012.

[Ale90] R. Alexander, Geometric methods in the study of irregularities of distribution, Combinatorica 10:115-136, 1990 [doi]

[Alo12] N. Alon. A non-linear lower bound for planar epsilon-nets. Discrete and Computational Geometry, 47(2):235–244, 2012.

[AloBFK92] N. Alon, I. Barany, Z. Furedi and D. J. Kleitman, Point selections and weak epsilon-nets for convex hulls, Comb. Prob. Comput. 1, 189-200, 1992.

[AloDOV03] N. Alon, G. Ding, B. Oporowski, and D. Vertigan, Partitioning into graphs with only small components, J. Combin. Theory Ser. B 87, 231–243, 2003.

[AloG86] N. Alon, E. Györi, The number of small semispaces of a finite set of points in the plane, Journal of Combinatorial Theory Series A 41:154-157, 1986 [doi]

[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] - 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+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] - 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

[ADEP18] Boris Aronov, Anirudh Donakonda, Esther Ezra, Rom Pinchasi, On Pseudo-disk Hypergraphs [arXiv]

[AroES10] Boris Aronov, Esther Ezra, and Micha Sharir, Small-size eps-nets for axis-parallel rectangles and boxes, SIAM J. Comput. 39 (7): 3248-3282, 2010

[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]

[AxeU16] M. Axenovich, T. Ueckerdt, Density of range capturing hypergraphs, JoCG 7, 21 pages, 2016. [JoCG]

[BalS19] J. Balogh, J. Samotij, An efficient container lemma [arXiv] arXiv.

[BalS18] J. Balogh, J. Solymosi, On the number of points in general position in the plane, Discrete Analysis 16, 20 pp, 2018 [arXiv] arXiv.

[Bec81] J. Beck, Balanced two-colorings of finite sets in the square I, Combinatorica (1981) 1: 327–335.

[Bec87] J. Beck, Irregularities of distribution, I. Acta Math. 159 (1987), 1--49.

[Bec88a] J. Beck, Irregularities of distribution. II. Proc. London Math. Soc. (3) 56 (1988), no. 1, 1–50.

[Bec88b] J. Beck, On irregularities of point sets in the unit square, Combinatorics (Eger, 1987), 63–74, Colloq. Math. Soc. Jnos Bolyai, 52, North-Holland, Amsterdam, 1988.

[Bec88c] J. Beck, On the discrepancy of convex plane sets, Monatsh. Math., 105:91–106, 1988.

[Ber72] C. Berge, Balanced matrices, Mathematical Programming 2:19-31, 1972 [doi]

[BBCP19] Ahmad Biniaz, Prosenjit Bose, Jean Cardinal and Michael Payne. Three-Coloring Three-Dimensional Uniform Hypergraphs, CCCG 2019, [preprint]

[BPRS10] B. Bollobás, D. Pritchard, T. Rothvoss, A. Scott, Cover-Decomposition and Polychromatic Numbers, SIAM J. Discrete Math. 27:240-256, 2013 [arXiv] - question is studied for abstract hypergraphs families.

[Bro04] H. Brönnimann, Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane, JCDCG 2004: 54–61.

[BukMN11] B. Bukh, J. Matousek, and G. Nivasch, Lower bounds for weak epsilon-nets and stair-convexity, Israel J. Math. 182, 199–228, 2011 [arXiv].

[BPR13] S. Buzaglo, R. Pinchasi, G. Rote, Topological hypergraphs, Thirty Essays on Geometric Graph Theory, (Ed. J. Pach), 71–81, Springer, New York, 2013 [preprint]

[BHP08] S. Buzaglo, R. Holzman, R. Pinchasi, On s-intersecting curves and related problems, SoCG '08, pages 79–84 [preprint]

[CKMU12] J. Cardinal, K. Knauer, P. Micek, T. Ueckerdt, Making triangles colorful, J. Comput. Geom. 4:240-246, 2013 [arXiv] - 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] - apart from main result, also shown that it is not possible to cover-decompose intervals with semi-online algorithm.

[CK11] J. Cardinal, M. Korman, Coloring planar homothets and three-dimensional hypergraphs, Comput. Geom. 46:1027-1035, 2013 [arXiv] - studies proper coloring of planar homothets.

[C12] T. Chan, Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set, SoCG 2012, 293–302 [preprint]

[ChaGKS12] T. M. Chan, E. Grant, J. Konemann, and M. Sharpe, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, SODA 2012, 1576–1585.

[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]

[CheFSS14] N. Chevallier, A. Fruchard, D. Schmitt, J.-C. Spehner, Separation by convex pseudocircles, SoCG '14, pages 444–453 [HAL]

[Cor35] J. G. van der Corput, Verteilungsfunktionen I and II, Akad. Wetensch. Amsterdam, Proc., 38:813–821 and 1058–1066, 1935.

[Dey98] T. K. Dey, Improved bounds for planar k-sets and related problems, Discrete and Computational Geometry 19: 373–382, 1998 [doi]

[Drm93] M. Drmota, Irregularities of distribution and convex sets, Grazer Math. Ber., 318:9–16, 1993.

[EMS09] M. Elekes, T. Mátrai, L. Soukup, On splitting infinite-fold covers, Fundamenta Mathematicae 212:95-127, 2011 [arXiv] - some results related to infinite cardinalities.

[EspJ14] L. Esperet and G. Joret, Colouring planar graphs with three colours and no large monochromatic components, Combinatorics, Probability and Computing, 23:551–570, 2014.

[F10] R. Fulek, Coloring geometric hypergraph defined by an arrangement of half-planes, CCCG, 71-74, 2010 [arXiv]

[GV09] M. Gibson, K. Varadarajan, Decomposing Coverings and the Planar Sensor Cover Problem, Discrete and Computational Geometry, 46:313-333, 2011 [arXiv]

[HS05] S. Har-Peled, S. Smorodisky, Conflict-free coloring of points and simple regions in the plane, Discrete Comput. Geom. 34:47–70, 2005.

[HauW87] D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete and Computational Geometry, 2:127–151, 1987.

[KS17] C. Keller, S. Smorodinsky, Conflict-free coloring of intersection graphs of geometric objects, [arXiv]

[KelS18] C. Keller, S. Smorodinsky, A new lower bound on Hadwiger-Debrunner numbers in the plane, [arXiv]

[K11] B. Keszegh, Coloring half-planes and bottomless rectangles, Computational Geometry: Theory and Applications, 45:495-507, 2012 [arXiv]

[K17] B. Keszegh, Coloring intersection hypergraphs of pseudo-disks, SoCG 2018, [arXiv]

[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] - certain online coloring algorithms do not exist and simpler proofs for some results of [K11].

[KP13] B. Keszegh, D. Pálvölgyi, Convex Polygons are Self-Coverable, Discrete and Computational 51(4):885-895, 2014 [arXiv]

[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]

[KP15] B. Keszegh, D. Pálvölgyi, More on Decomposing Coverings by Octants, Journal of Computational Geometry 6:300-315, 2015 [arXiv]

[KP11] B. Keszegh, D. Pálvölgyi, Octants are Cover Decomposable, Discrete and Computational Geometry, 47:598-609, 2012 [arXiv] - 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] - 12^2^k-fold coverings with octants decompose into k coverings.

[K13] I. Kovács, Indecomposable coverings with homothetic polygons, Discrete and Computational Geometry, 53:817-824, 2015 [arXiv]

[KP16] B. Keszegh, D. Pálvölgyi, Proper Coloring of Geometric Hypergraphs, SoCG 2017, 1-15, [arXiv]

[K17b] N. Kumar, On the minimum edge size for 2-colorability and realizability of hypergraphs by axis-parallel rectangles, CCCG 2017: 226-231, [proceedings]

[KleMRV97] J. Kleinberg, R. Motwani, P. Raghavan, and S. Venkatasubramanian, Storage management for evolving databases, FOCS 1997, 353–362.

[KomPW92] J. Komlós, J. Pach, and G. J. Woeginger, Almost tight bounds for epsilon-nets, Discrete and Computational Geometry, 7:163–173, 1992.

[KT14] I. Kovács, G. Tóth, Multiple coverings with closed polygons, Electronic Journal of Combinatorics 22:18 pages, 2015 [arXiv]

[Lau08] Sören Laue, Geometric Set Cover and Hitting Sets for Polytopes in R3, STACS 2008: 479-490.

[LiuO18] Chun-Hung Liu, Sang-il Oum, Partitioning H-minor free graphs into three subgraphs with no large components, Journal of Combinatorial Theory B 128:114-133, 2018 [doi]

[Mat91] J. Matoušek, Lower Bounds on the Length of Monotone Paths in Arrangements, J. Discrete Comput Geom 6:129-134 (1991) [doi]

[Mat92] J. Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, 2(3):169–186, 1992.

[Mat95] J. Matoušek, Tight upper bounds for the discrepancy of half-spaces, J. Discrete Comput Geom 13: 593-601, 1995 [doi]

[Mat99] J. Matoušek, On the Discrepancy for Boxes and Polytopes, Monatshefte für Mathematik 127: 325–336, 1999 [doi]

[MatSW90] J. Matoušek, R. Seidel, and E. Welzl, How to net a lot with little: Small epsilon-nets for disks and halfspaces, SoCG 1990, 16–22.

[MatWW93] J. Matoušek, E. Welzl, L. Wernisch, Discrepancy and ε-approximations for bounded VC-dimension, Combinatorica 13 (1993), 455–466.

[MP86] P. Mani-Levitska, J. Pach, Decomposition problems for multiple coverings with unit balls, manuscript, 1986 [some parts] - merged into [PP13].

[MusDG18] N.H. Mustafa, K. Dutta, A. Ghosh, A Simple Proof of Optimal Epsilon Nets, Combinatorica 38: 1269–1277, 2018 [HAL]

[NaszT10] Márton Naszódi, Steven Taschuk, On the transversal number and VC-dimension of families of positive homothets of a convex body, Discrete Mathematics, 310:77-82, 2010 [doi].

[NewNN12] Alantha Newman, Ofer Neiman, and Aleksandar Nikolov, Beck's Three Permutations Conjecture: A Counterexample and Some Consequences, FOCS 2012.

[Nik17] A. Nikolov, Tighter Bounds for the Discrepancy of Boxes and Polytopes, Mathematika, 63(3), 1091-1113, 2017.

[P86] J. Pach, Covering the plane with convex polygons, Discrete and Computational Geometry 1:73-81, 1986 - centrally symmetric convex sets are cover-decomposable.

[P80] J. Pach, Decomposition of multiple packing and covering, Diskrete Geometrie, 2. Kolloq. Math. Inst. Univ. Salzburg, 1980 [scan.ps]

[PP13] J. Pach, D. Pálvölgyi, Unsplittable coverings in the plane, Advances in Mathematics 302:433-457, 2016 [arXiv] - 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.

[PT08] J. Pach, G. Tardos, Coloring axis-parallel rectangles, J. of Combinatorial Theory, Series A, 117(6):776-782, 2010 [journal]

[PT13] J. Pach and G. Tardos, Tight lower bounds for the size of epsilon-nets, Journal of the AMS, 26:645–658, 2013.

[PTT05] J. Pach, G. Tardos, G. Tóth, Indecomposable coverings, Canadian Mathematical Bulletin, 52:451-463, 2009 [preprint]

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

[P13] D. Pálvölgyi, Indecomposable coverings with unit discs [arXiv:1310.6900v1] - merged into [PP13].

[P10] D. Pálvölgyi. Indecomposable coverings with concave polygons, Discrete and Computational Geometry 44:577-588, 2010 [preprint]

[PT10] D. Pálvölgyi, G. Tóth, Convex polygons are cover-decomposable, Discrete and Computational Geometry 43:483-496, 2010 [preprint]

[PV19] D. Pálvölgyi, N. Varadarajan, Colouring bottomless rectangles and arborescences [arXiv:1912.05251]

[PayW13] M. S. Payne, D. R. Wood, On the general position subset selection problem, SIAM J. Discrete Math., 27(4):1727–1733, 2013 [arxiv] - studies max independent for bounded clique in 3-uniform ptXline.

[Pec85] G. W. Peck, On k-sets in the plane, Discrete Mathematics 56:73-74, 1985 [preprint]

[Pin14] R. Pinchasi, A finite family of pseudodiscs must include a "small" pseudodisc, SIAM Journal on Discrete Mathematics 28:1930-1934, 2014 [preprint]

[PinG14] R. Pinchasi, G. Rote, On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs, Israel Journal of Mathematics 172:337-348, 2009 [doi]

[PyrR08] E. Pyrga and S. Ray, New existence proofs for ε-nets, SoCG 2008, 199–207.

[RamR18] R. Raman, S. Ray, Planar Support for Non-piercing Regions and Applications, ESA 2018, 14 pages. [DROPS] - planar support for non-piercing regions.

[Rot54] K. F. Roth, On irregularities of distribution, Mathematika, 1:73–79, 1954.

[Rot80] K. F. Roth, On irregularities of distribution IV. Ada Arith., 37: 67-75, 1980.

[Rub19] N. Rubin, An improved bound for weak epsilon-nets in the plane, FOCS 2018 [arxiv]

[Sch72] W. M. Schmidt. On irregularities of distribution VII. Acta Arith., 21:45–50, 1972.

[Sch75] W. M. Schmidt. On irregularities of distribution IX. Acta Arith., 27:385–396, 1975.

[Sha91] M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom., 6(4):593-613, 1991 [doi]

[ShaST01] M. Sharir, S. Smorodinsky, G. Tardos, An improved bound for k-sets in three dimensions, Discrete Comput. Geom., 26(2):195–204, 2001 [doi]

[Skr98] Skriganov, Ergodic theory on SL(n), diophantine approximations and anomalies in the lattice point problem, Invent math 132:1–72, 1998 [doi]

[S07] S. Smorodinsky, On the chromatic number of geometric hypergraphs, SIAM Journal on Discrete Mathematics 21(3):676-687, 2007 [journal]

[SY10] S. Smorodinsky, Y. Yuditsky, Polychromatic Coloring for Half-Planes, J. Comb. Theory, Ser. A 119:146-154, 2012 [arXiv]

[Spe85] J. Spencer, Six standard deviations suffice, Transactions of the American Mathematical Society, 289(2):679–706, 1985.

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

[T01] G. Tóth, Point sets with many k-sets, Discrete and Computational Geometry 26:187-194, 2001.

[Var10] K. R. Varadarajan, Weighted geometric set cover via quasi-uniform sampling, STOC 2010, 641–648.

[W65] G. Wegner, 0ber eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner, Israel J. of Math 3: 187-198, 1965.