Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning

Given a set system (X,R) such that every pair of sets in R have large symmetric difference, the Shallow Packing Lemma gives an upper bound on |R| as a function of the shallow-cell complexity of R. In this paper, we first present a matching lower bound. Then we give our main theorem, an application of the Shallow Packing Lemma: given a semialgebraic set system (X,R) with shallow-cell complexity φ(⋅,⋅) and a parameter ϵ>0, there exists a collection, called an ϵ-Mnet, consisting of $O(1ϵφ(O(1ϵ),O(1)))$ subsets of X, each of size $Ω(ϵ|X|)$, such that any $R∈R$ with $|R|≥ϵ|X|$ contains at least one set in this collection. We observe that as an immediate corollary an alternate proof of the optimal ϵ-net bound follows.