# The geometric hypergraph zoo (beta)

Toggle info:

Show only:

Search:

Show also:

Layout:

#### Definitions and legend

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., '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$$

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

#### Bibliography

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