Lower Bounds for Pinning Lines by Balls (Extended Abstract)

Otfried Cheong (1) , Xavier Goaoc (2) , Andreas Holmsen (1)

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

It is known that if n>=2d pairwise disjoint balls in R^d have a unique line ℓ intersecting them in a given order <, one can always remove a ball so that ℓ remains the only line intersecting the balls in the order induced by <. We show that the constant 2d is best possible, in any dimension, and derive lower bounds on Helly numbers for sets of line transversals to disjoint balls in arbitrary dimension.

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

Otfried Cheong, Xavier Goaoc, Andreas Holmsen. Lower Bounds for Pinning Lines by Balls (Extended Abstract). European Conference on Combinatorics, Graph Theory and Applications - EuroComb 2009, Sep 2009, Bordeaux, France. pp.567-571, ⟨10.1016/j.endm.2009.07.094⟩. ⟨inria-00431437⟩