A Constant Bound for Geometric Permutations of Disjoint Unit Balls

Abstract. We prove that a set of n disjoint unit balls in R^d admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry. The constant bound significantly improves upon the Θ (n^d-1) bound for disjoint balls of unrestricted radii.

Authors and Affiliations

1. Faculty of Mathematics, Technion, Haifa 32000, Israel meirk@techunix.technion.ac.il , , , , , , IL

   Katchalski

2. Computer Science Department, University of California, Santa Barbara, CA 93106, USA suri@cs.ucsb.edu , , , , , , US

   Suri

3. Compaq Systems Research Center, 130 Lytton Ave, Palo Alto, CA 94301, USA yzhou@pa.dec.com, , , , , , US

   Zhou

Reprints and permissions