KAIST Discrete Math Seminar

We prove Helly-type theorems for line transversals to disjoint unit spheres in R^d. In particular, we show that a family of n ≥ 2d disjoint unit spheres in R^d has a line transversal if, for some ordering of the balls, any subfamily of 2d balls admits a line transversal consistent with this ordering. We also discuss generalizations that drop the ordering requirement and to spheres with arbitrary radius.