2023/11/27 by Jung, Attila, Pálvölgyi, Dömötör
#52A35 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.15646
We prove a fractional Helly theorem for k-flats intersecting fat convex sets. A family F of sets is said to be ρ-fat if every set in the family contains a ball and is contained in a ball such that the ratio of the radii of these balls is bounded by ρ. We prove that for every dimension d and positive reals ρ and α there exists a positive β=β(d,ρ, α) such that if F is a finite family of ρ-fat convex sets in ℝd and an α-fraction of the (k+2)-size subfamilies from F can be hit by a k-flat, then there is a k-flat that intersects at least a β-fraction of the sets of F. We prove spherical and colorful variants of the above results and prove a (p,k+2)-theorem for k-flats intersecting balls.