The geometric hypergraph zoo (beta)

---

Toggle info: χ χₘ m₂ mₖ size VC-dim τₛ \(\varepsilon\)-net discr

---

Show only: all    selected
pt/* */pt translate homothet pseudo mₖ=O(k)

---

Search: show only show also restrict to   

---

Show also: parents children parents and children
ascendants descendants ascendants and descendants

geometric hypergraphs

\({\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., 'ptXtransl 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\)

geometric families

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\).

chromatic number, \(\chi\)

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\).

m-chromatic number, \(\chi_m, m_2\)

\({\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 coloring, \(m_k\)

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\).

size of the hypergraph, \(e,e_k,e_{\le k},a\)

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\)-dimension

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\).

shallow hitting set, \(\tau_s\)

\(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, weak-\(\varepsilon\)-net

\(\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, \(discr\), \(D\)

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.

legend

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, Discrete and Computational Geometry 58, 757–784 (2017). (Conference version 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, Computational Geometry: Theory and Applications 92, 2021 [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. [arXiv]
[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.
[BCDGLR20] B. Bosek, S. Czerwinski, M. Debski, J. Grytczuk, Z. Lonc, P. Rzazewski. Coloring chain hypergraphs, [in: 20 YEARS OF THE FACULTY OF MATHEMATICS AND INFORMATION SCIENCE, Warsaw], 2020
[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]
[CKMPUV20] J. Cardinal, K. Knauer, P. Micek, D. Pálvölgyi, T. Ueckerdt, N. Varadarajan, Colouring bottomless rectangles and arborescences, Proceedings of EuroCG 2020 [arxiv] - mk=O(k) for some special bottomless rectangle families and impossibility of certain sweeping algorithms
[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.
[CheT21] V. Chekan, T. Ueckerdt, Polychromatic Colorings of Unions of Geometric Hypergraphs [arXiv] - characterization of which unions of subsets of following 8 primal (pt/*) families have bounded \(m_k\): horizontal/vertical strips, 4 types of quadrants, bottomless/topless rectangles
[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.
[DP20] D. Damásdi, D. Pálvölgyi, Realizing an m-uniform four-chromatic hypergraph with disks. [arXiv]
[DP21] D. Damásdi, D. Pálvölgyi, Three-chromatic geometric hypergraphs. [arxiv] (Earlier result for only disks: Unit disks hypergraphs are three-colorable. Eurocomb 2021.)
[Dey98] T. K. Dey, Improved bounds for planar k-sets and related problems, Discrete and Computational Geometry 19: 373–382, 1998 [doi]
[DHH14] M. G. Dobbins, A. Holmsen, A. Hubard, The Erdős-Szekeres problem for non-crossing convex sets, Mathematika, 60: 463-484, 2014. [arxiv]
[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. Order, 33(3): 389-409, 2016. (Conference version in LNCS 7741 (SOFSEM 2013): 292-306, 2013.) [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 Geometry 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, Discrete and Computational Geometry 62(3) (2019), 674-689; 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.
[PhD] D. Pálvölgyi, Decomposition of Geometric Set Systems and Graphs. PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2010. [arXiv:1009.4641]
[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]
[PlaU23] Tim Planken, Torsten Ueckerdt, Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets [arxiv]
[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.
[T23] I. Tomon, Coloring lines and Delaunay graphs with respect to boxes, Random Structures and Algorithms, 2023 [doi] - lower bound on coloring points wrt. axis-parallel boxes in higher dimensions.
[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.
[WD81] R. S. Wenocur and R. M. Dudley, Some special Vapnik-Chervonenkis classes, Discrete Mathematics 33:313-318, 1981.