Helly-type Theorems for Line transversals to Disjoint Unit Balls (Extended abstract)

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 >= 2d disjoint unit balls in Rd has a line transversal if, for some ordering of the balls, every subfamily of 2d balls admits a line transversal consistent with . We also prove that a family of n >= 4d − 1 disjoint unit balls in R^d admits a line transversal if every 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 (Extended abstract). European Workshop on Computational Geometry, Mar 2006, Delphi, Greece. pp.87--89. ⟨inria-00189019⟩