2023/10/30 by Planken, Tim, Ueckerdt, Torsten
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Hypergraphs
paper · doi:10.48550/arxiv.2310.19982
A range family R is a family of subsets of ℝd, like all halfplanes, or all unit disks. Given a range family R, we consider the m-uniform range capturing hypergraphs H(V,R,m) whose vertex-sets V are finite sets of points in ℝd with any m vertices forming a hyperedge e whenever e = V ∩ R for some R ∈ R. Given additionally an integer k ≥ 2, we seek to find the minimum m = mR(k) such that every H(V,R,m) admits a polychromatic k-coloring of its vertices, that is, where every hyperedge contains at least one point of each color. Clearly, mR(k) ≥ k and the gold standard is an upper bound mR(k) = O(k) that is linear in k. A t-shallow hitting set in H(V,R,m) is a subset S ⊆ V such that 1 ≤ |e ∩ S| ≤ t for each hyperedge e; i.e., every hyperedge is hit at least once but at most t times by S. We show for several range families R the existence of t-shallow hitting sets in every H(V,R,m) with t being a constant only depending on R. This in particular proves that mR(k) ≤ tk = O(k) in such cases, improving previous polynomial bounds in k. Particularly, we prove this for the range families of all axis-aligned strips in ℝd, all bottomless and topless rectangles in ℝ2, and for all unit-height axis-aligned rectangles in ℝ2.