Finite unions of convex sets are a central object of study in discrete and computational geometry. In this paper we initiate a systematic study of complements of such unions - i.e., sets of the form S = ℝ^d ⧵ (∪_{i=1}^n K_i), where K_i are convex sets. In the first part of the paper we study isolated points in S, whose number is related to the Betti numbers of ∪_{i=1}^n K_i and to its non-convexity properties. We obtain upper bounds on the number of such points, which are sharp for n = 3 and significantly improve previous bounds of Lawrence and Morris (2009) for all n ≪ 2^d/d. In the second part of the paper we study coverings of S by well-behaved sets. We show that S can be covered by at most g(d,n) flats of different dimensions, in such a way that each x ∈ S is covered by a flat whose dimension equals the "local dimension" of S in the neighborhood of x. Furthermore, we determine the structure of a minimum cover that satisfies this property. Then, we study quantitative aspects of this minimum cover and obtain sharp upper bounds on its size in various settings.

Abstract A major research area in discrete geometry is to consider the best way to partition the d -dimensional Euclidean space $$\mathbb {R}^d$$ R d under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $$\mathbb {R}^d$$ R d to a discrete subset of representative values. Specifically, we study partitions of $$\mathbb {R}^d$$ R d into bounded-size tiles colored by one of k colors, such that tiles of the same color have a distance of at least t from each other. Such tilings allow for error-resilient rounding, as two points of the same color and distance less than t from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors k and the distance t , for various dimensions d . On the qualitative side, we show that in $$\mathbb {R}^d$$ R d , using $$k=d+1$$ k = d + 1 colors is both sufficient and necessary to achieve $$t>0$$ t > 0 . On the quantitative side, we achieve numerous upper and lower bounds on t as a function of k . In particular, for $$d=3,4,8,24$$ d = 3 , 4 , 8 , 24 , we obtain sharp asymptotic bounds on t , as $$k \rightarrow \infty $$ k → ∞ . We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat’s connector-free lemma, and Čech cohomology.

In this paper we study the hypergraph Zarankiewicz’s problem in a geometric setting - for r-partite intersection hypergraphs of families of geometric objects. Our main results are essentially sharp bounds for families of axis-parallel boxes in ℝ^d and families of pseudo-discs. For axis-parallel boxes, we obtain the sharp bound O_{d,t}(n^{r-1}((log n)/(log log n))^{d-1}). The best previous bound was larger by a factor of about (log n)^{d(2^{r-1}-2)}. For pseudo-discs, we obtain the bound O_t(n^{r-1}(log n)^{r-2}), which is sharp up to logarithmic factors. As this hypergraph has no algebraic structure, no improvement of Erdős' 60-year-old O(n^{r-(1/t^{r-1})}) bound was known for this setting. Futhermore, even in the special case of discs for which the semialgebraic structure can be used, our result improves the best known result by a factor of Ω̃(n^{(2r-2)/(3r-2)}). To obtain our results, we use the recently improved results for the graph Zarankiewicz’s problem in the corresponding settings, along with a variety of combinatorial and geometric techniques, including shallow cuttings, biclique covers, transversals, and planarity.

A family ℱ of sets satisfies the (p,q)-property if among every p members of ℱ, some q can be pierced by a single point. The celebrated (p,q)-theorem of Alon and Kleitman asserts that for any p ≥ q ≥ d+1, any family ℱ of compact convex sets in ℝ^d that satisfies the (p,q)-property can be pierced by a finite number c(p,q,d) of points. A similar theorem with respect to piercing by (d-1)-dimensional flats, called (d-1)-transversals, was obtained by Alon and Kalai. In this paper we prove the following result, which can be viewed as an (ℵ₀,k+2)-theorem with respect to k-transversals: Let ℱ be an infinite family of sets in ℝ^d such that each A ∈ ℱ contains a ball of radius r and is contained in a ball of radius R, and let 0 ≤ k < d. If among every ℵ₀ elements of ℱ, some k+2 can be pierced by a k-dimensional flat, then ℱ can be pierced by a finite number of k-dimensional flats. This is the first (p,q)-theorem in which the assumption is weakened to an (∞,⋅) assumption. Our proofs combine geometric and topological tools.

We study a natural generalization of the classical $\epsilon$-net problem (Haussler--Welzl 1987), which we call the "$\epsilon$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $\epsilon\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\epsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\epsilon$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\epsilon$-$t$-net of size $O(\frac{ (1+\log t)d}{\epsilon} \log \frac{1}{\epsilon})$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\epsilon})$-sized $\epsilon$-$t$-nets. We also present an explicit construction of $\epsilon$-$t$-nets (including $\epsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\epsilon$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

For $n\geq s> r\geq 1$ and $k\geq 2$, write $n \rightarrow (s)_{k}^r$ if every hyperedge coloring with $k$ colors of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by M. Axenovich, A. Gyárfás, H. Liu, and D. Mubayi [ Discrete Math., 322 (2014), pp. 69--77] and P. Erdös, A. Hajnal, A. Máté, and R. Rado, [ Combinatorial set theory: Partition Relations for Cardinals, Elsevier, Amsterdam, 1984] we show that $if r \geq 3 and n \nrightarrow (s)_k^r, then 2^n \nrightarrow (s+1)_{k+3}^{r+1}.$ This improves some of the known lower bounds on multicolor hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of coloring all $r$-subsets of $V$ such that no hyperedge of size $\geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colors necessary in terms of the chromatic number $\chi(H)$. In particular we show that this number is $O(\log^{(r-1)} (r \chi(H)) + r)$, where $\log^{y}$ is the $\log$ function applied $y$ times.

For a family ℱ of non-empty sets in ℝ^d, the Krasnoselskii number of ℱ is the smallest m such that for any S ∈ ℱ, if every m or fewer points of S are visible from a common point in S, then any finite subset of S is visible from a single point. More than 35 years ago, Peterson asked whether there exists a Krasnoselskii number for general sets in ℝ^d. The best known positive result is Krasnoselskii number 3 for closed sets in the plane, and the best known negative result is that if a Krasnoselskii number for general sets in ℝ^d exists, it cannot be smaller than (d+1)². In this paper we answer Peterson’s question in the negative by showing that there is no Krasnoselskii number for the family of all sets in ℝ². The proof is non-constructive, and uses transfinite induction and the well-ordering theorem. In addition, we consider Krasnoselskii numbers with respect to visibility through polygonal paths of length ≤ n, for which an analogue of Krasnoselskii’s theorem for compact simply connected sets was proved by Magazanik and Perles. We show, by an explicit construction, that for any n ≥ 2, there is no Krasnoselskii number for the family of compact sets in ℝ² with respect to visibility through paths of length ≤ n. (Here the counterexamples are finite unions of line segments.)

A major research area in discrete geometry is to consider the best way to partition the $d$-dimensional Euclidean space $\mathbb{R}^d$ under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $\mathbb{R}^d$ to a discrete subset of representative values. Specifically, we study partitions of $\mathbb{R}^d$ into bounded-size tiles colored by one of $k$ colors, such that tiles of the same color have a distance of at least $t$ from each other. Such tilings allow for \emph{error-resilient} rounding, as two points of the same color and distance less than $t$ from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors $k$ and the distance $t$, for various dimensions $d$. On the qualitative side, we show that in $\mathbb{R}^d$, using $k=d+1$ colors is both sufficient and necessary to achieve $t>0$. On the quantitative side, we achieve numerous upper and lower bounds on $t$ as a function of $k$. In particular, for $d=3,4,8,24$, we obtain sharp asymptotic bounds on $t$, as $k \to \infty$. We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat's connector-free lemma, and Čech cohomology.

We study a natural generalization of the classical $ε$-net problem (Haussler--Welzl 1987), which we call the "$ε$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $ε\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $εn$ contains a set in $S$. When $t=1$, this corresponds to the $ε$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $ε$-$t$-net of size $O(\frac{ (1+\log t)d}ε \log \frac{1}ε)$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}ε)$-sized $ε$-$t$-nets. We also present an explicit construction of $ε$-$t$-nets (including $ε$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $ε$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

A family \(\mathcal {F}\) of sets is said to satisfy the ( p , q )-property if among any p sets of \(\mathcal {F}\) some q have a non-empty intersection. The celebrated ( p , q )-theorem of Alon and Kleitman asserts that any family of compact convex sets in \(\mathbb {R}^d\) that satisfies the ( p , q )-property for some \(q \ge d+1\) , can be pierced by a fixed number (independent of the size of the family) \(f_d(p,q)\) of points. The minimum such piercing number is denoted by \(\mathsf {HD} _d(p,q)\) . Already in 1957, Hadwiger and Debrunner showed that whenever \(q>\frac{d-1}{d}\,p+1\) the piercing number is \(\mathsf {HD} _d(p,q)=p-q+1\) ; no tight bounds on \(\mathsf {HD} _d(p,q)\) were found ever since. While for an arbitrary family of compact convex sets in \(\mathbb {R}^d\) , \(d \ge 2\) , a ( p , 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific classes. The best-studied among them is the class of axis-parallel boxes in \(\mathbb {R}^d\) , and specifically, axis-parallel rectangles in the plane. Wegner (Israel J Math 3:187–198, 1965 ) and (independently) Dol’nikov (Sibirsk Mat Ž 13(6):1272–1283, 1972 ) used a ( p , 2)-theorem for axis-parallel rectangles to show that \(\mathsf {HD} _\mathrm{{rect}}(p,q)=p-q+1\) holds for all \(q \ge \sqrt{2p}\) . These are the only values of q for which \(\mathsf {HD} _\mathrm{{rect}}(p,q)\) is known exactly. In this paper we present a general method which allows using a ( p , 2)-theorem as a bootstrapping to obtain a tight ( p , q )-theorem, for classes with Helly number 2, even without assuming that the sets in the class are convex or compact. To demonstrate the strength of this method, we show that \(\mathsf {HD} _{d\text {-box}}(p,q)=p-q+1\) holds for all \(q > c' \log ^{d-1} p\) , and in particular, \(\mathsf {HD} _\mathrm{{rect}}(p,q)=p-q+1\) holds for all \(q \ge 7 \log _2 p\) (compared to \(q \ge \sqrt{2p}\) , obtained by Wegner and Dol’nikov more than 40 years ago). In addition, for several classes, we present improved ( p , 2)-theorems, some of which can be used as a bootstrapping to obtain tight ( p , q )-theorems. In particular, we show that any class \(\mathcal {G}\) of compact convex sets in \(\mathbb {R}^d\) with Helly number 2 admits a ( p , 2)-theorem with piercing number \(O(p^{2d-1})\) , and thus, satisfies \(\mathrm {HD}_{\mathcal {G}}(p,q) = p-q+1\) , for a universal constant c .

In 2002, Even et al. introduced and studied the notion of conflict-free colorings of geometrically defined hypergraphs. They motivated it by frequency assignment problems in cellular networks. This notion has been extensively studied since then. A conflict-free coloring of a graph is a coloring of its vertices such that the neighborhood (pointed or closed) of each vertex contains a vertex whose color differs from the colors of all other vertices in that neighborhood. In this paper we study conflict-free colorings of intersection graphs of geometric objects. We show that any intersection graph of n pseudo-discs in the plane admits a conflict-free coloring with $$O(\log n)$$ colors, with respect to both closed and pointed neighborhoods. We also show that the latter bound is asymptotically sharp. Using our methods, we obtain the following strengthening of the two main results of Even et al.: Any family $$\mathcal {F}$$ of n discs in the plane can be colored with $$O(\log n)$$ colors in such a way that for any disc B in the plane, not necessarily from $$\mathcal {F}$$ , the set of discs in $$\mathcal {F}$$ that intersect B contains a uniquely-colored element. In view of the original motivation to study such colorings, this strengthening suggests further applications to frequency assignment in wireless networks. Finally, we present bounds on the number of colors needed for conflict-free colorings of other classes of intersection graphs, including intersection graphs of axis-parallel rectangles and of $$\rho $$ -fat objects in the plane.

Let HDd(p, q) denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in ℝd which satisfy the (p, q)-property (p ≥ q ≥ d + 1). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that HDd(p, q) exists for all P ≥ q ≥ d +1. Specifically, they prove that HDd(p,d + 1) is This paper has two parts. In the first part we present several improved bounds on HDd(p, q). In particular, we obtain the first near tight estimate of HDd(p, q) for an extended range of values of (p, q) since the 1957 Hadwiger-Debrunner theorem. In the second part we prove a (p, 2)-theorem for families in ℝ2 with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property. It is not likely that our constant factor approximation can be improved to a PTAS as MAX-CLIQUE for intersection graphs of fat ellipses is known to be APX-HARD and fat ellipses have sub-quadratic union complexity.