Lower Bounds to Helly Numbers of Line Transversals to Disjoint Congruent Balls

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

1 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1 pairwise disjoint unit balls in R^d with the property that every subfamily of size 2d-2 admits a transversal, yet any line misses at least one member of the family. This answers a question of Danzer from 1957.

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

Otfried Cheong, Xavier Goaoc, Andreas Holmsen. Lower Bounds to Helly Numbers of Line Transversals to Disjoint Congruent Balls. Israel Journal of Mathematics, 2012, 190 (1), pp.213-228. ⟨inria-00518035⟩