Polychromatic Colorings of Unions of Geometric Hypergraphs

Abstract

A polychromatic k-coloring of a hypergraph assigns to each vertex one of k colors in such a way that every hyperedge contains all the colors. A range capturing hypergraph is an m-uniform hypergraph whose vertices are points in the plane and whose hyperedges are those m-subsets of points that can be separated by some geometric object of a particular type, such as axis-aligned rectangles, from the remaining points. Polychromatic k-colorings of m-uniform range capturing hypergraphs are motivated by the study of weak $\varepsilon$-nets and cover decomposability problems.

We show that the hypergraphs in which each hyperedge is determined by a bottomless rectangle or by a horizontal strip in general do not allow for polychromatic colorings. This strengthens the corresponding result of Chen, Pach, Szegedy, and Tardos [Random Struct. Algorithms, 34:11–23, 2009] for axis-aligned rectangles, and gives the first explicit (not randomized) construction of non-2-colorable hypergraphs defined by axis-aligned rectangles of arbitrarily large uniformity.

In general we consider unions of range capturing hypergraphs, each defined by a type of unbounded axis-aligned rectangles. For each combination of types, we show that the unions of such hypergraphs either admit polychromatic k-colorings for $m = O(k)$, $m = O(k \log k)$, $m = O(k^{8.75})$, or do not admit in general polychromatic 2-colorings for any m.

1 Introduction

A range capturing hypergraph is a geometric hypergraph $\mathcal {H}(V,{\mathcal {R}})$ defined by a finite point set $V \subset \mathbb {R}^2$ in the plane and a family $\mathcal {R}$ of subsets of $\mathbb {R}^2$, called ranges. Possible ranges are for example the family $\mathcal {R}$ of all axis-aligned rectangles, all horizontal strips, or all translates of the first (north-east) quadrant. Given the points V and ranges $\mathcal {R}$, the hypergraph $\mathcal {H}(V,\mathcal {R}) = (V,\mathcal {E})$ has V as its vertex set and a subset $E \subset V$ forms a hyperedge $E\in \mathcal {E}$ whenever there exists a range $R\in \mathcal {R}$ with $E = V \cap R$. That is, a subset of points forms a hyperedge whenever these points and no other points are captured by some range from family $\mathcal {R}$.

For a positive integer m, we are then interested in the m-uniform subhypergraph $\mathcal {H}(V,\mathcal {R},m)$ given by all hyperedges of size exactly m. In particular, we investigate polychromatic vertex colorings $c:V \rightarrow [k]$ in k colors of $\mathcal {H}(V,\mathcal {R},m)$ for different families of ranges $\mathcal {R}$ and different values of m. A vertex coloring is polychromatic if every hyperedge contains at least one vertex of each color. Polychromatic colorings of range capturing hypergraphs were first studied in the 1980s by Pach [17, 18] in the context of cover-decomposability problems. These also relate to the planar sensor cover problem [10] and weak $\varepsilon$-nets [20, 26]. Polychromatic colorings of geometric hypergraphs then experienced a major revival during the past decade with several breakthrough advances [2,3,4,5,6, 11,12,13,14,15, 19, 23,24,25]. The interested reader is referred to the (slightly outdated) survey article [22] and the excellent website [1] which contains numerous references.

Here, we focus on polychromatic k-colorings for range capturing hypergraphs with given range family $\mathcal {R}$. In particular, we investigate the following question.

Question 1

Given $\mathcal {R}$ and k, what is the smallest $m = m(k)$ such that for every finite point set $V \subset \mathbb {R}^2$ the hypergraph $\mathcal {H}(V,\mathcal {R},m)$ admits a polychromatic k-coloring?

Of course, $m(k) \geqslant k$, while $m(k)=\infty$ is also possible. It also holds that $m(k) \leqslant m(k+1)$ for any k: given a polychromatic $(k+1)$-coloring of a hypergraph, we can recolor every vertex of color $k+1$ arbitrarily, after that every hyperedge will still contain all colors in $1, \dots , k$. For all range families considered here, we either show that $m(k) < \infty$ for every $k \geqslant 1$ or already $m(2) = \infty$ holds. Note that in the latter case, there are range capturing hypergraphs that are not properly¹ 2-colorable, even for arbitrarily large uniformity m. So although we do not consider proper colorings explicitly in this work, our results imply that the chromatic number of certain hypergraphs is larger than 2.

1.1 Related Work

There is a rich literature on range capturing hypergraphs, their polychromatic colorings, and answers to Question 1. Let us list the positive results (meaning $m(k)<\infty$ for all k) that are relevant here, whilst defining the respective ranges.

• For halfplanes $\mathcal {R}= \{ \{ (x,y) \in \mathbb {R}^2 \mid 1 \leqslant ax + by \} \mid a,b \in \mathbb {R}\}$ it is known that $m(k) = 2k-1$ [25].

• For south-west quadrants $\mathcal {R}= \{\{(x,y) \in \mathbb {R}^2 \mid x \leqslant a \text { and } y \leqslant b\} \mid a,b \in \mathbb {R}\}$ it is easy to prove that $m(k) = k$, see e.g. [12].

• For axis-aligned strips $\mathcal {R}= \{\{(x,y) \in \mathbb {R}^2 \mid a_1 \leqslant x \leqslant a_2\} \mid a_1,a_2 \in \mathbb {R}\} \cup \{\{(x,y) \in \mathbb {R}^2 \mid a_1 \leqslant y \leqslant a_2\} \mid a_1,a_2 \in \mathbb {R}\}$ it is known that $m(k) \leqslant 2k-1$ [3].

• For bottomless rectangles $\mathcal {R}= \{\{(x,y) \in \mathbb {R}^2 \mid a_1 \leqslant x \leqslant a_2 \text { and } y \leqslant b\} \mid a_1,a_2,b \in \mathbb {R}\}$ it is known that $1.67k \leqslant m(k) \leqslant 3k-2$ [4].

• For axis-aligned squares $\mathcal {R}= \{ \{(x,y) \in \mathbb {R}^2 \mid a \leqslant x \leqslant a+s \text { and } b \leqslant y \leqslant b+s\} \mid a,b,s \in \mathbb {R}\}$ it is known that $m(k) \leqslant O(k^{8.75})$ [2].

On the contrary, let us also list the negative results (meaning $m(k) = \infty$ for some k) that are relevant here. In all cases, it is shown that already $m(2)=\infty$ holds. This means that there is a sequence $(\mathcal {H}_m)_{m \geqslant 1}$ of m-uniform hypergraphs such that for each $m \geqslant 1$ the hypergraph $\mathcal {H}_m$ admits no polychromatic 2-coloring and we have that $\mathcal {H}_m$ is a subhypergraph of $\mathcal {H}(V_m,\mathcal {R},m)$ for some finite point set $V_m$. If the latter property holds, we say that $\mathcal {H}_m$ can be realized with $\mathcal {R}$. One such sequence are the m-ary tree hypergraphs, defined on the vertices of a complete m-ary tree of height m, where for each non-leaf vertex, its m children form a hyperedge, and for each leaf vertex, its m ancestors (including itself) form a hyperedge (introduced by Pach, Tardos, and Tóth [21]). A second such sequence is due to Pálvölgyi [23] (published in [19]), for which we do not repeat the formal definition here and simply refer to them as the 2-size hypergraphs as their inductive construction involves hyperedges of two possibly different sizes.

• For strips $\mathcal {R}= \{ \{(x,y) \in \mathbb {R}^2 \mid 1 \leqslant ax + by \leqslant c\} \mid a,b,c \in \mathbb {R}\}$ it is known that $m(2)=\infty$ as every m-ary tree hypergraph can be realized with strips [21].

• For unit disks $\mathcal {R}= \{ \{(x,y) \in \mathbb {R}^2 \mid (x-a)^2 + (y-b)^2 \leqslant 1\} \mid a,b \in \mathbb {R}\}$ it is known that $m(2)=\infty$ as every 2-size hypergraph can be realized with unit disks [19].

Finally, for axis-aligned rectangles $\mathcal {R}= \{ \{(x,y) \in \mathbb {R}^2 \mid a_1 \leqslant x \leqslant a_2 \text { and } b_1 \leqslant y \leqslant b_2\} \mid a_1,a_2,b_1,b_2 \in \mathbb {R}\}$ it is also known that $m(2) = \infty$. See Theorem 2 below. However, the only known proof of Theorem 2 was a probabilistic argument and no explicit construction of a sequence $(\mathcal {H}_m)_{m \geqslant 1}$ of m-uniform hypergraphs realizable by axis-aligned rectangles that admit no polychromatic 2-coloring was known before this work.

Theorem 2

(Chen et al. [8]). For the family $\mathcal {R}$ of all axis-aligned rectangles it holds that $m(2) = \infty$. That is, for every $m \geqslant 1$ there exists a finite point set $V \subset \mathbb {R}^2$ such that for every 2-coloring of V some axis-aligned rectangle contains m points of V, all of the same color.

1.2 Our Results

In this paper we consider range families $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$ that are the union of two range families $\mathcal {R}_1$, $\mathcal {R}_2$. The corresponding hypergraph $\mathcal {H}(V,\mathcal {R},m)$ is then the union of the hypergraphs $\mathcal {H}(V,\mathcal {R}_1,m)$ and $\mathcal {H}(V,\mathcal {R}_2,m)$ on the same vertex set $V \subset \mathbb {R}^2$. Clearly, if $\mathcal {H}(V,\mathcal {R},m)$ is polychromatic k-colorable, then so are $\mathcal {H}(V,\mathcal {R}_1,m)$ and $\mathcal {H}(V,\mathcal {R}_2,m)$. But the converse is not necessarily true and this shall be the subject of our investigations.

Aloupis et al. [3] show that if $\mathcal {R}_1$ and $\mathcal {R}_2$ admit so-called m-hitting k-sets, then we can conclude that $m(k) \leqslant m < \infty$ for $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$; see Lemma 3. This is for example the case for all horizontal (resp. vertical) strips, but already fails for all south-west quadrants. In Sect. 3 we then consider all possible families of unbounded axis-aligned rectangles, such as axis-aligned strips, all four types of quadrants, or bottomless rectangles. We determine exactly for which subset of those, when taking $\mathcal {R}$ as their union, it holds that $m(k) < \infty$.

In particular, we show in Sect. 3.1 that $m(k) = \infty$ for all $k \geqslant 2$ when $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$ is the union of $\mathcal {R}_1$ all bottomless rectangles and $\mathcal {R}_2$ all horizontal strips. Our proof gives a new sequence $(\mathcal {H}_m)_{m \geqslant 1}$ of m-uniform hypergraphs that admit a geometric realization for simple ranges, but do not admit any polychromatic 2-coloring. On the positive side, we show in Sect. 3.2 that (up to symmetry) all other subsets of unbounded axis-aligned rectangles (excluding the above pair) admit polychromatic k-colorings for every k. Here, our proof relies on so-called shallow hitting sets and in particular a variant in which a subset of V hits every hyperedge defined by $\mathcal {R}_1$ at least once and every hyperedge defined by $\mathcal {R}_1 \cup \mathcal {R}_2$ at most a constant (usually 2 or 3) number of times.

Assumptions and Notation. Before we start, let us briefly mention some convenient facts that are usually assumed, and which we also assume throughout our paper: Whenever a range family $\mathcal {R}$ is given, we only consider point sets V that are in general position with respect to $\mathcal {R}$. For us, this means that the points in V have pairwise different x-coordinates, pairwise different y-coordinates, and also pairwise different sums of x- and y-coordinates. Secondly, all range families $\mathcal {R}$ that we consider here are shrinkable, meaning that whenever a set $X \subseteq V$ of i points is captured by a range in $\mathcal {R}$, then also some subset of $i-1$ points of X is captured by a range in $\mathcal {R}$. This means that for every polychromatic k-coloring of $\mathcal {H}(V,\mathcal {R},m)$, every range in $\mathcal {R}$ capturing m or more points of V, contains at least one point of each color. Finally, for every set $X \subseteq V$ captured by a range in $\mathcal {R}$, we implicitly associate to X one arbitrary but fixed such range $R \in \mathcal {R}$ with $V \cap R = X$. In particular, we shall sometimes consider the range R for a given hyperedge E of $\mathcal {H}(V,\mathcal {R},m)$.

2 Polychromatic Colorings for Two Range Families

Let $\mathcal {R}_1,\mathcal {R}_2$ be two families of ranges, for each of which it is known that $m(k) < \infty$ for any $k \geqslant 1$. We seek to investigate whether also for $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$ we have $m(k) < \infty$. First, we identify a simple sufficient condition.

For fixed $k,m,\mathcal {R}$, we say that we have m-hitting k-sets with respect to $\mathcal {R}$ if the following holds. For every $V \subset \mathbb {R}^2$, there exist pairwise disjoint k-subsets of V such that every hyperedge of $\mathcal {H}(V,\mathcal {R},m)$ fully contains at least one such k-subset. Clearly, if we have m-hitting k-sets, then $m(k) \leqslant m$ since we can simply use all colors $1,\ldots , k$ on each such k-subset (and color any remaining vertex arbitrarily). Crucially, if two range families $\mathcal {R}_1$ and $\mathcal {R}_2$ admit m-hitting k-sets, then $m(k) \leqslant m$ also carries over to their union $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$. This has already been implicitly used in [3].

Lemma 3

(Aloupis et al. [3]). For fixed k, m, suppose that we have m-hitting k-sets with respect to $\mathcal {R}_1$ and m-hitting k-sets with respect to $\mathcal {R}_2$. Then for $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$ it holds that $m(k) \leqslant m$.

For example, Lemma 3 gives $m(k) \leqslant 2k-1$ when $\mathcal {R}$ consists of all axis-parallel strips [3]. In fact, for the vertical (resp. horizontal) strips it suffices to group the points into k-sets with consecutive x-coordinates (resp. y-coordinates).

Somewhat unfortunately, m-hitting k-sets appear to be very rare. Already for the range family $\mathcal {R}$ of all south-west quadrants, for which one can easily show that $m(k)=k$, we do not even have m-hitting 2-sets for any m. This will follow from the following result, which will also be useful later.

Lemma 4

Let T be a rooted tree, and $\mathcal {H}(T)$ be the hypergraph on V(T) where for each leaf vertex its ancestors (including itself) form a hyperedge. Then $\mathcal {H}(T)$ can be realized with the family $\mathcal {R}$ of all south-west quadrants.

Moreover, the root is the bottommost and leftmost point and the children of each non-leaf vertex lie on a diagonal line of slope $-1$.

Proof

We do induction on the height of T, with height 1 being a trivial case of a single vertex. For height at least 2, remove the root r from T to obtain new trees $T_1,\ldots ,T_p$, each of smaller height and rooted at a child of r. By induction, there are point sets in the plane for each $\mathcal {H}(T_i)$, $i=1,\ldots ,p$, with each respective root being bottommost and leftmost. We scale each of these points sets uniformly until the bounding box of each of them has width as well as height less than 1. For every $i \in [p]$, we put the point set for $\mathcal {H}(T_i)$ into the plane so that the root of $T_i$ has the coordinate $(i, p - i)$. Finally, we place r in the origin. This gives the desired realization.

Note: in the end we can slightly perturb the point set so that it still realizes $\mathcal {H}(T)$ but it is in general position and the children of every non-leaf vertex are captured by a diagonal strip of slope $-1$.    $\square$

Corollary 5

For any $k, m \geqslant 2$ and for the family $\mathcal {R}$ of all south-west quadrants, we do not have m-hitting k-sets in general.

Proof

Take the rooted complete binary tree $T_m$ of height m, for which $\mathcal {H}(T_m)$ is realizable with south-west quadrants by Lemma 4. By induction on m, we show that $\mathcal {H}(T_m)$ does not have m-hitting 2-sets. This is trivial for $m=2$. Otherwise, any collection of disjoint 2-subsets either avoids the root r, or pairs r with a vertex in one of the two subtrees of $T_m$ below r. In any case, there is a subtree T below r, none of whose vertices is paired with r and hence, there exist m-hitting 2-sets of $\mathcal {H}(T)$. Note that T is a complete binary tree of height $m-1$, so $T = T_{m-1}$. But then $\mathcal {H}(T_{m-1})$ admits $(m-1)$-hitting 2-sets too – a contradiction to the induction hypothesis.

Finally, if $\mathcal {H}(T_m)$ had m-hitting k-sets for some $k \geqslant 2$, then taking a 2-subset of every k-set in it, would result in m-hitting 2-sets of $\mathcal {H}(T_m)$.    $\square$

Corollary 6

For any $k, m \geqslant 2$ and for the family $\mathcal {R}$ of all halfplanes, we do not have m-hitting k-sets in general.

Proof

By a result of Middendorf and Pfeiffer [16], every range capturing hypergraph for south-west quadrants can also be realized by halfplanes and the result follows from Corollary 5.    $\square$

To summarize, parallel strips have m-hitting k-sets, but quadrants do not. Hence, we cannot apply Lemma 3 to conclude that $m(k) < \infty$ when we consider $\mathcal {R}$ to be the union of all quadrants of one direction and all parallel strips of one direction. In Sect. 3 we shall prove that indeed $m(k) < \infty$ for the union of all quadrants and strips, however only provided that the strips are axis-aligned. In fact, if they are not, this is not necessarily true.

Corollary 7

Let $\mathcal {R}_1$ be the family of all south-west quadrants and $\mathcal {R}_2 = \{ \{(x,y) \in \mathbb {R}^2 \mid a \leqslant x+y \leqslant b\} \mid a,b \in \mathbb {R}\}$ be the family of all diagonal strips of slope $-1$.

Then for $\mathcal {R}= \mathcal {R}_1 \cup \mathcal {R}_2$ we have $m(2) = \infty$.

Proof

Given m, consider the rooted complete m-ary tree $T_m$ of height m. By Lemma 4, $V(T_m)$ can be placed in the plane such that for each leaf vertex, its m ancestors (including itself) are captured by a south-west quadrant, and for each non-leaf vertex, its m children are captured by a diagonal strip of slope $-1$. Hence, every m-ary tree hypergraph $\mathcal {H}_m$ can be realized with $\mathcal {R}$. By [21] $\mathcal {H}_m$ admits no polychromatic 2-coloring for any m, which gives the result.    $\square$

3 Families of Unbounded Rectangles

In this section we consider the following range families of unbounded rectangles:

• all (axis-aligned) south-west quadrants $\mathcal {R}_\textrm{SW}$,

• similarly all south-east $\mathcal {R}_\textrm{SE}$, north-east $\mathcal {R}_\textrm{NE}$, north-west $\mathcal {R}_\textrm{NW}$ quadrants,

• all horizontal $\mathcal {R}_\textrm{HS}$, vertical $\mathcal {R}_\textrm{VS}$, diagonal $\mathcal {R}_\textrm{DS}$ strips of slope $-1$,

• all bottomless rectangles $\mathcal {R}_\textrm{BL}$, and finally all topless rectangles $\mathcal {R}_\textrm{TL} = \{ \{(x,y) \in \mathbb {R}^2 \mid a_1 \leqslant x \leqslant a_2, y \geqslant b\} \mid a_1,a_2,b \in \mathbb {R}\}$.

Observe that if a point set is captured by a south-east quadrant Q, then it is also captured by a bottomless rectangle having the same top and left sides as Q and whose right side lies to the right of every point in the vertex set. Analogous statements hold for other quadrants and vertical strips. Further, note that each of the above range families, except the diagonal strips $\mathcal {R}_\textrm{DS}$, is a special case of the family of all axis-aligned rectangles. Recall that for the family of all axis-aligned rectangles, it is known that $m(2) = \infty$ [8]. Here we are interested in the maximal subsets of $\{ \mathcal {R}_\textrm{SW}, \mathcal {R}_\textrm{SE}, \mathcal {R}_\textrm{NE}, \mathcal {R}_\textrm{NW}, \mathcal {R}_\textrm{HS}, \mathcal {R}_\textrm{VS}, \mathcal {R}_\textrm{BL}, \mathcal {R}_\textrm{TL}\}$ so that for the union $\mathcal {R}$ of all these ranges, it still holds that $m(k) < \infty$ for all k. In fact, we shall show that for $\mathcal {R}= \mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{HS}$ we have $m(2) = \infty$, strengthening the result for axis-aligned rectangles [8]. On the other hand, for $\mathcal {R}= \mathcal {R}_\textrm{SW} \cup \mathcal {R}_\textrm{SE} \cup \mathcal {R}_\textrm{NE} \cup \mathcal {R}_\textrm{NW} \cup \mathcal {R}_\textrm{HS} \cup \mathcal {R}_\textrm{VS}$, i.e., the union of all quadrants and axis-aligned strips, we have $m(k) < \infty$ for all k, strengthening the results for south-west quadrants [12] and axis-aligned strips [3]. Secondly, for $\mathcal {R}= \mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{TL}$, i.e., the union of bottomless and topless rectangles (which also contains all quadrants and all vertical strips), we again have $m(k) < \infty$ for all k, thus strengthening the result for bottomless rectangles [4]. Using symmetries, this covers all cases of the considered unbounded axis-aligned rectangles. We complement our results by also considering the diagonal strips $\mathcal {R}_\textrm{DS}$ and recall that we already know by Corollary 7 that for $\mathcal {R}= \mathcal {R}_\textrm{DS} \cup \mathcal {R}_\textrm{SW}$ we have $m(2) = \infty$.

3.1 The Case with No Polychromatic Coloring: Bottomless Rectangles and Horizontal Strips

For every $m \in \mathbb {N}$, we will define a rooted forest $F_m$ consisting of $m^m$ trees whose vertices are partitioned into a set of the so-called stages (the forest $F_2$ is illustrated in Fig. 1(a)). The vertices of a stage S will be totally ordered and we denote this ordering by $<_S$. All vertices of a stage S will have the same distance to the root of the corresponding tree, we refer to this distance as the level of S. Every stage on level $j \in \{0, \dots , m-1\}$ will consist of $m^{m-j}$ vertices.

We start with $m^m$ roots, one for each tree in $F_m$. They build the unique stage on level 0 and they are ordered in an arbitrary but fixed way. After that, for $j = 1, \dots , m - 1$, every stage S on level $j - 1$, and every subset $S' \in {S \atopwithdelims ()m^{m-j}}$, we add a new stage $T(S')$ on level j consisting of $m^{m-j}$ new vertices so that every vertex in $S'$ gets exactly one child from $T(S')$ and the vertices of $T(S')$ are ordered by $<_{T(S')}$ as their parents by $<_S$. As a result, every vertex in S gets a child for every $(m^{m-j})$-subset of S in which it occurs.

Now we can define the hypergraph $\mathcal {H}_m = (V, \mathcal {E})$. The vertex set V is exactly the vertex set $V(F_m)$ of the forest $F_m$. There are two types of hyperedges. First, stage-hyperedges $\mathcal {E}_s$: for every stage S, each m consecutive vertices in $<_S$ constitute a stage-hyperedge. Second, the path-hyperedges $\mathcal {E}_p$: every root-to-leaf path in $F_m$ forms a path-hyperedge. Then, the set of hyperedges is defined as $\mathcal {E}= \mathcal {E}_s \cup \mathcal {E}_p$. Note that $\mathcal {H}_m = (V,\mathcal {E})$ is indeed m-uniform. For a vertex v, let ${\text {root}}(v)$ denote the root of the tree in $F_m$ containing v, and ${\text {path}}(v) \subset V$ denote the set of vertices on the path from v to ${\text {root}}(v)$ in $F_m$.

Theorem 8

For every $m \in \mathbb {N}$ the m-uniform hypergraph $\mathcal {H}_m = (V, \mathcal {E}= \mathcal {E}_s \cup \mathcal {E}_p)$ admits no polychromatic coloring with 2 colors.

Fig. 1.

(a) The forest $F_2$ and the desired embedding of $\mathcal {H}_2$. (b) Sketch of the embedding of $\mathcal {H}_m$ for the proof of Theorem 9. (Color figure online)

Proof

We show that every 2-coloring of V that makes all stage-hyperedges polychromatic produces a monochromatic path-hyperedge. Let ${\phi : V \rightarrow \{\text {red, blue}\}}$ be such a coloring. The key observation is that a stage S on level j (i.e., one that contains $m^{m-j}$ vertices) can be partitioned into $m^{m-j} / m = m^{m-j-1}$ disjoint stage-hyperedges and hence, it contains at least $m^{m-j-1}$ red vertices.

We prove for $j \in \{0, \dots , m-1\}$ that there is a stage $S_j$ on level j and a subset $B_j \subset S_j$ such that $|B_j| = m^{m-j-1}$ and for every $v \in B_j$, the vertices in ${\text {path}}(v)$ are all red. For $j = 0$, the stage consisting of roots contains at least $m^{m-1}$ red roots and these vertices have the desired property. Assuming the statement for some j, consider the stage $S_{j+1} = T(B_j)$ and a set $B_{j+1}$ of $m^{m-j-2}$ red points in it. By definition, each of these points v has its parent in $B_j$ and hence, all vertices in ${\text {path}}(v)$ are red, proving the statement for $j+1$. By induction, it holds for $j = m-1$ and hence, there is a vertex on level $m-1$ (i.e., a leaf) whose root-to-leaf path is all red. So $\mathcal {H}_m$ admits no polychromatic 2-coloring.    $\square$

Theorem 9

For every $m \in \mathbb {N}$ the m-uniform hypergraph $\mathcal {H}_m = (V, \mathcal {E}= \mathcal {E}_s \cup \mathcal {E}_p)$ admits a realization with bottomless rectangles and horizontal strips.

Proof

For a point $p \in \mathbb {R}^2$, let x(p) and y(p) denote its x- resp. y-coordinate. A sequence of points $p_1, \dots , p_t$ is ascending (resp. descending) if ${x(p_1)< \dots < x(p_t)}$ and ${y(p_1)< \dots < y(p_t)}$ (resp. ${x(p_1)< \dots < x(p_t)}$ and ${y(p_1)> \dots > y(p_t)}$). Writing about the vertices of a stage S, we always refer to their ordering in $<_S$. We shall embed each stage S of $\mathcal {H}_m$ into a closed horizontal strip, denoted $H_S$, in such a way that $H_S \,\cap \, H_{S'} = \emptyset$ whenever $S \ne S'$. Note that this way, the embedded stages are vertically ordered with some available space between any two consecutive ones. For illustration see Fig. 1.

First, we embed the roots of $F_m$, i.e., the unique stage on level 0, as an ascending sequence in a horizontal strip for this stage. After that, until all stages are embedded, we choose some stage S that has already been embedded but the stages $T_1, \ldots , T_r$ containing its children not yet and in one step we embed $T_1,\ldots ,T_r$ as follows. We pick a thin horizontal strip H between $H_S$ and the strip above (if it exists) and within H identify disjoint horizontal strips $H_1, \dots , H_r$. Then, every $T_i$ is embedded inside $H_i$ so that every vertex gets initially the same x-coordinate as its parent and the vertices of $T_i$ build an ascending sequence in $H_i$. After that, for every $v \in S$ we slightly shift all children of v to the right so that they build a descending sequence but the ordering of x-coordinates relative to all other vertices remains unchanged.

The arising embedding ensures the following two properties. First, every stage-hyperedge is captured by a horizontal strip. Second, for every vertex v, the bottomless rectangle B(v) with top-right corner v and ${\text {root}}(v)$ on the left side captures exactly ${\text {path}}(v)$, in particular every path-hyperedge is then captured by a bottomless rectangle. In the full version of the paper [7], we prove that these two properties indeed hold and this concludes the proof.    $\square$

3.2 The Cases with Polychromatic Colorings

First, recall the result of Ackerman et al. [2] that for the range family $\mathcal {R}_\textrm{SQ}$ of all axis-aligned squares, we have $m(k) = O(k^{8.75})$. This already seals the deal for bottomless and topless rectangles.

Theorem 10

For the family $\mathcal {R}= \mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{TL}$ of all bottomless and topless rectangles, we have $m(k) = O(k^{8.75})$ for all k.

Proof

Let V be a finite point set and let m be arbitrary. For every bottomless (resp. topless) rectangle capturing a hyperedge of $\mathcal {H}= \mathcal {H}(V, \mathcal {R}, m)$, we introduce a bottom (resp. top) side below the bottommost (resp. above the topmost) point in V so that these rectangles are bounded now. After that, we stretch the plane horizontally until the width of every aforementioned rectangle becomes larger than its height and obtain the point set $V'$. This stretching preserves the ordering of x- and y-coordinates of the points so that the set of hyperedges captured by $\mathcal {R}$ remains the same. Finally, we pick every (now bounded) bottomless (resp. topless) rectangle capturing a hyperedge of $\mathcal {H}$ and shift its bottom (resp. top) side down (resp. up) until it becomes a square. Now for every hyperedge in $\mathcal {H}$, there is an axis-aligned square capturing it and hence, a hyperedge in $\mathcal {H}' = (V', \mathcal {R}_\textrm{SQ}, m)$. Thus, each polychromatic coloring of $\mathcal {H}'$ yields a polychromatic coloring of $\mathcal {H}$ and this concludes the proof.    $\square$

For the remaining cases, we utilize so-called shallow hitting sets. For a positive integer t, a subset X of vertices of a hypergraph $\mathcal {H}$ is a t-shallow hitting set if every hyperedge of $\mathcal {H}$ contains at least one and at most t points from X. It is known for example that for $\mathcal {R}$ being the family of all halfplanes, every range capturing hypergraph $\mathcal {H}(V,\mathcal {R},m)$ admits a 2-shallow hitting set [25], which implies that $m(k) \leqslant 2k-1$ in this case. In general, we have the following.

Lemma 11

(Keszegh and Pálvölgyi [13]). Suppose that for a shrinkable range family $\mathcal {R}$, every hypergraph $\mathcal {H}(V,\mathcal {R},m)$ admits a t-shallow hitting set. Then $m(k) \leqslant (k-1)t + 1$.

Remark 1

Lemma 11 states that if t-shallow hitting sets exist (for a global constant t), then $m(k) = O(k)$. However, it is not clear whether the converse is also true, for example when $\mathcal {R}$ is the family of all bottomless rectangles. Keszegh and Pálvölgyi [13] construct for this family range capturing hypergraphs without shallow hitting sets, but their constructed hypergraphs are not uniform. In fact, one can extract 3-shallow hitting sets for axis-aligned strips from the m-hitting k-sets for horizontal and vertical strips for $m=2k-1$: since every hyperedge of $\mathcal {H}(V,\mathcal {R}_\textrm{HS} \cup \mathcal {R}_\textrm{VS})$ of size $2k-1$ or 2k is hit by at most three of the m-hitting k-sets, each color of the resulting k-coloring is a 3-shallow hitting set. To the best of our knowledge, it is open whether all $\mathcal {H}(V,\mathcal {R},m)$ admit shallow hitting sets for the bottomless rectangles $\mathcal {R}= \mathcal {R}_\textrm{BL}$.

Recall that for the family $\mathcal {R}_\textrm{NW}$ of all north-west quadrants we have $m(k)=k$. In such a polychromatic coloring, every color class is a 1-shallow hitting set. Besides $\mathcal {R}_\textrm{NW}$, we want to consider other range families, and thus are interested in t-shallow hitting sets for $\mathcal {R}_\textrm{NW}$ that additionally do not hit other ranges, such as axis-parallel strips or other quadrants, too often. Let $E_t(V, m)$ (resp. $E_b(V, m)$) denote the set of m topmost (resp. bottommost) points in V.

Lemma 12

For the family $\mathcal {R}_\textrm{NW}$ of all north-west quadrants, every hypergraph $\mathcal {H}(V,\mathcal {R}_\textrm{NW},m)$ admits a 2-shallow hitting set X such that the points $x_1,\ldots ,x_n$ in X have decreasing x-coordinates and decreasing y-coordinates, and

• (i) $x_1$ is the leftmost point of $E_t(V, m)$,

• (ii) the hyperedge $E_t(V, m)$ is hit by X exactly once,

• (iii) for any two consecutive points $x_j,x_{j+1}$ in X, the bottomless rectangle $B_j$ with top-right corner $x_j$ and $x_{j+1}$ on the left side satisfies $|B_j \cap V| \geqslant m+1$, and

• (iv) for any three consecutive points $x_j,x_{j+1},x_{j+2}$ in X, the axis-aligned rectangle $R_j$ with top-right corner $x_j$ and bottom-left corner $x_{j+2}$ satisfies $|R_j \cap V| \geqslant m+2$.

Proof

For each hyperedge of $\mathcal {H}(V,\mathcal {R}_\textrm{NW},m)$ consider a fixed north-west quadrant capturing these m points of V. These quadrants can be indexed $Q_1,\ldots ,Q_\alpha$ along their apices with decreasing x-coordinates (and hence also y-coordinates). I.e., $Q_1$ contains the topmost m points of V, while $Q_\alpha$ contains the leftmost m points of V. See Fig. 2 for an illustrative example.

Fig. 2.

Sketch for the proof of Lemma 12 for $m = 3$. The vertices in X are red.

Starting with $X = \emptyset$, we go through the north-west quadrants from $Q_1$ to $Q_\alpha$, and whenever $Q_i$ does not contain any point of X, we add the leftmost point of $Q_i \,\cap \, V$ to X. Label the points in X by $x_1,\ldots ,x_n$ in the order of their addition to X. Along this order, the points have decreasing x-coordinates and decreasing y-coordinates. Clearly, X is a hitting set of $\mathcal {H}(V,\mathcal {R}_\textrm{NW},m)$ and satisfies (i).

Since $x_1$ is the leftmost point of $Q_1$, $x_j$ does not belong to $Q_1$ for every $j \in \{2, \dots , n\}$. Since $Q_1$ contains exactly vertices of $E_t(V, m)$, the corresponding hyperedge is hit by X exactly once. This proves (ii).

For any two consecutive points $x_j,x_{j+1}$ in X, consider the bottomless rectangle $B_j$ with top-right corner $x_j$ and $x_{j+1}$ on the left side. Then $|B_j \cap V| \geqslant m+1$ as $B_j$ contains $x_j$ and all points of the north-west quadrant Q for which we added $x_{j+1}$ to X. This proves (iii).

Moreover, every point in $Q \,\cap \, V$ lies above $x_{j+2}$ (if it exists), as $x_{j+1}$ is leftmost in Q. Thus, the axis-aligned rectangle $R_j$ with top-right corner $x_j$ and bottom-left corner $x_{j+2}$ contains $x_j$, all the m points in $Q \cap V$, and $x_{j+2}$. This proves (iv) and also implies that X is 2-shallow.    $\square$

Let us explain the properties of this lemma. Suppose we have a south-west quadrant hit at least twice by X. Then it contains two consecutive points from X and by (iii) this quadrant contains at least $m+1$ points and hence it does not capture a hyperedge of $\mathcal {H}(V, \mathcal {R}_\mathrm{{SW}}, m)$. Similarly, a horizontal strip containing at least three points from X does not capture a hyperedge of $\mathcal {H}(V, \mathcal {R}_\mathrm{{HS}}, m)$ by (iv). Finally, since $x_1$ is the rightmost point of X and it is also the leftmost point of $E_t(V, m)$, every hyperedge $E \ne E_t(V, m)$ of $\mathcal {H}(V, \mathcal {R}_\mathrm{{NE}}, m)$ is not hit by X at all. For symmetry reasons, statements analogous to the above lemma hold for other types of quadrants and ranges as well. We provide a full description of these properties in the full version of the paper [7].

Intuitively speaking, Lemma 12 allows us to color some points in V, in such a way that every north-west quadrant already contains all colors, while other ranges, such as bottomless rectangles or diagonal strips, have most of their points still uncolored. The following lemma (proven in the full version of the paper [7]) provides a framework which can then be applied to color various range families.

Lemma 13

Let $\mathcal {R}_1, \mathcal {R}_2$ be shrinkable range families, $f: \mathbb {N}\rightarrow \mathbb {N}$ be a function, and $s, t \in \mathbb {N}$ be such that:

• (i) For every $k \in \mathbb {N}$, it holds that $m_{\mathcal {R}_2}(k) \leqslant f(k)$.

• (ii) And for every point set V and every $m \in \mathbb {N}$, the hypergraph $\mathcal {H}(V, \mathcal {R}_1, m)$ admits a t-shallow hitting set $S \subseteq V$ such that every hyperedge of $\mathcal {H}(V, \mathcal {R}_2, m)$ is hit at most s times by S.

Then for every $k \in \mathbb {N}$, we have $\quad m_{\mathcal {R}_1 \cup \mathcal {R}_2}(k) \leqslant f(k) + k \max (s, t)$.

With Lemma 13 in place, we obtain the upper bounds for several range families:

Theorem 14

• (i) For the range family $\mathcal {R}_\mathrm{{BL}} \cup \mathcal {R}_\mathrm{{NW}} \cup \mathcal {R}_\mathrm{{NE}}$, we have $m(k) \leqslant 5k-2$ for all k.

• (ii) For the range family $\mathcal {R}_\mathrm{{HS}} \cup \mathcal {R}_\mathrm{{VS}} \cup \mathcal {R}_\mathrm{{NW}} \cup \mathcal {R}_\mathrm{{NE}} \cup \mathcal {R}_\mathrm{{SW}} \cup \mathcal {R}_\mathrm{{SE}}$, we have $m(k) \leqslant 10k-1$ for all k.

• (iii) For the range family $\mathcal {R}_\mathrm{{HS}} \cup \mathcal {R}_\mathrm{{VS}} \cup \mathcal {R}_\mathrm{{DS}} \cup \mathcal {R}_\mathrm{{NW}} \cup \mathcal {R}_\mathrm{{SE}}$, we have $m(k) \leqslant \lceil 4k \ln k + k \ln 3 \rceil + 4k$ for all k.

Proof

In all cases, we combine Lemmas 12 and 13 with some known results.

Now we prove (i). By Lemma 12, for every point set V and every $m \in \mathbb {N}$, there exist subsets $S_\mathrm{{NW}}, S_\mathrm{{NE}} \subseteq V$ such that $S_\mathrm{{NW}} \cup S_\mathrm{{NE}}$ is a 2-shallow hitting set of $\mathcal {H}(V, \mathcal {R}_\mathrm{{NW}} \cup \mathcal {R}_\mathrm{{NE}}, m)$ and every hyperedge of $\mathcal {H}(V, \mathcal {R}_\mathrm{{BL}}, m)$ is hit at most $1+1=2$ times by this set (see [7] for more details). So we use $s = t = 2$. Further, we set $\mathcal {R}_1 = \mathcal {R}_\mathrm{{NW}} \cup \mathcal {R}_\mathrm{{NE}}$, $\mathcal {R}_2 = \mathcal {R}_\mathrm{{BL}}$ and we use $f(k) = 3k-2$ for all k. By [4], we know that for every k, we have $m_{\mathcal {R}_2}(k) \leqslant f(k)$. So by Lemma 13 for every k we have $\quad m(k) \leqslant (3k - 2) + k\max (2,2) = 5k - 2$.

The remaining two claims are proven similarly in the full version of the paper [7]. There we use that for axis-aligned strips we have $m(k) \leqslant 2k-1$ and for strips in three directions, we have $\quad m(k) \leqslant \lceil 4k \ln k + k \ln 3 \rceil$ for all k [3].    $\square$

4 Concluding Remarks

We have considered the range families $\mathcal {R}_\textrm{SW},\mathcal {R}_\textrm{SE},\mathcal {R}_\textrm{NE},\mathcal {R}_\textrm{NW}$ of all south-west, south-east, north-east, and north-west quadrants, the range families $\mathcal {R}_\textrm{HS},\mathcal {R}_\textrm{VS}$ of all horizontal and vertical strips, and the range families $\mathcal {R}_\textrm{BL},\mathcal {R}_\textrm{TL}$ of all bottomless and topless rectangles, each being a special case of axis-aligned rectangles.

For every single family $\mathcal {R}$ in this list it is known that $m(k) = O(k)$, meaning that for every finite point set V the m-uniform hypergraph $\mathcal {H}(V,\mathcal {R},m)$ admits a polychromatic k-coloring as long as $m = \varOmega (k)$.

By Theorems 8 and 9 range capturing hypergraphs with respect to $\mathcal {R}= \mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{HS}$, i.e., bottomless rectangles and horizontal strips, do not even admit polychromatic 2-colorings. In other words $m(k) = \infty$ for all $k \geqslant 2$ in that case. On the other hand, by Theorems 10 and 14 such polychromatic k-colorings exist for every k (i.e., $m(k) < \infty$) whenever $\mathcal {R}$ is the union of any subset of $\{\mathcal {R}_\textrm{SW},\mathcal {R}_\textrm{SE},\mathcal {R}_\textrm{NE},\mathcal {R}_\textrm{NW},\mathcal {R}_\textrm{HS},\mathcal {R}_\textrm{VS},\mathcal {R}_\textrm{BL},\mathcal {R}_\textrm{TL}\}$ that does not include both $\mathcal {R}_\textrm{BL}$ and $\mathcal {R}_\textrm{HS}$, nor any rotation of that pair. (As horizontal strips form a special case of both 90-degree rotations of bottomless rectangles, our results also cover these left-unbounded and right-unbounded axis-aligned rectangles.)

In general, we observe the same behavior as for other range families in the literature: Either $m(k) < \infty$ holds for every k or already $m(2) = \infty$. It remains an interesting open problem to determine whether in general $m(2)<\infty$ always implies $m(k)<\infty$ for all k. In the positive cases, our upper bounds on m(k) are linear in k, except when $\mathcal {R}$ contains strips of three different directions or bottomless and topless rectangles. It is worth noting that no range family $\mathcal {R}$ is known for which $m(2) < \infty$ but $m(k) \in \omega (k)$. Such a candidate could be $\mathcal {R}= \mathcal {R}_\textrm{HS} \cup \mathcal {R}_\textrm{VS} \cup \mathcal {R}_\textrm{DS}$ or $\mathcal {R}= \mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{TL}$.

We suggest further investigations of shallow hitting sets in range capturing hypergraphs. To the best of our knowledge, their existence might be equivalent to m(k) being linear in k. In particular, do bottomless rectangles (for which it is known that $m(k) \in O(k)$ [4]) allow for shallow hitting sets? And do octants in 3D (for which shallow hitting sets are known not to exist [6]) have $m(k) \in O(k)$?

Finally, let us remark that the probabilistic construction of Chen et al. [8] for the range family $\mathcal {R}$ of all axis-aligned rectangles shows that the hypergraphs $\mathcal {H}(V,\mathcal {R},m)$ even have arbitrary large chromatic number for any fixed m, while our explicit construction for the sub-family $\mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{HS}$ only shows that the chromatic number is at least 3. In fact, the Union Lemma of Damasdi and Pálvölgyi [9] states that if $\mathcal {H}$ is the union of any $k-1$ hypergraphs, each of which admits a polychromatic k-coloring, then $\mathcal {H}$ has a proper k-coloring. In particular, every hypergraph $\mathcal {H}(V,\mathcal {R}_\textrm{BL} \cup \mathcal {R}_\textrm{HS},m)$ has chromatic number at most 3 for $m \geqslant 4$, and every hypergraph $\mathcal {H}(V,\mathcal {R},m)$ has chromatic number at most 5 for $m \geqslant 10$ when $\mathcal {R}$ is the union of all unbounded axis-aligned rectangles.