k-Dimensional Transversals for Fat Convex Sets

Jung, Attila and Pálvölgyi, Dömötör (2025) k-Dimensional Transversals for Fat Convex Sets. In: Leibniz International Proceedings in Informatics, LIPIcs. Leibniz International Proceedings in Informatics, LIPIcs (332). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, No.-61. ISBN 9783959773706

Preview

Text LIPIcs.SoCG.2025.61.pdf - Published Version Available under License Creative Commons Attribution. Download (777kB) | Preview

Abstract

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 Rd 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. © Attila Jung and Dömötör Pálvölgyi.

Actions (login required)

Edit Item