Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

Otfried Cheong (1) , Xavier Goaoc (2) , Andreas Holmsen (3) , Sylvain Petitjean (2)

1 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
3 UiB - Department of Mathematics [Bergen]

We prove Helly-type theorems for line transversals to disjoint unit balls in $\R^{d}$. In particular, we show that a family of $n \geq 2d$ disjoint unit balls in $\R^d$ has a line transversal if, for some ordering $\prec$ of the balls, any subfamily of $2d$ balls admits a line transversal consistent with $\prec$. We also prove that a family of $n \geq 4d-1$ disjoint unit balls in $\R^d$ admits a line transversal if any subfamily of size $4d-1$ admits a transversal.

Domaines: Géométrie algorithmique [cs.CG]

Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean. Helly-Type Theorems for Line Transversals to Disjoint Unit Balls. Discrete and Computational Geometry, 2008, 39 (1-3), pp.194-212. ⟨inria-00103856⟩