3532 articles – 5253 references  [version française]

inria-00103856, version 1

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

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

Discrete and Computational Geometry 39, 1-3 (2008) 194-212

Abstract: 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.

  • 1:  Department of Electrical Engineering [Korea Advanced Institute of Science and Technology] (KAIST)
  • Korea Advanced Institute of Science and Technology
  • 2:  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 3:  Department of Mathematics, Faculty of Mathematics and Natural Sciences
  • University of Bergen
  • Domain : Computer Science/Computational Geometry
 
  • inria-00103856, version 1
  • http://hal.inria.fr/inria-00103856
  • oai:hal.inria.fr:inria-00103856
  • From: Xavier Goaoc <>
  • Submitted on: Tuesday, 6 February 2007 16:06:31
  • Updated on: Monday, 23 May 2011 13:40:10