The Harmony of Spheres
Otfried Cheong · Canadian Conference on Computational Geometry · 2007
Let F = {X1, . . . , Xn} be a family of disjoint compact convex sets in R. An oriented straight line ` that intersects every Xi is called a (line) transversal to F . A transversal naturally induces an ordering of the elements of F , this ordering, together with its reverse (which is induced by the same line with opposite orientation), is called a geometric permutation. Geometric transversal theory studies properties of line transversals, and of families of objects admitting line transversals—see the handbook chapter by Wenger for a survey of this area [6]. Topics of interest are a characterization of the geometric permutations that a given family of objects can admit, and Helly-type theorems of the form: If every subfamily of F of size at most k admits a line transversal, then F must admit a line transversal. In this talk we discuss recent results on transversals to disjoint spheres (balls) in three and more dimensions. Katchalski et al. [5] had proven in 2003 that a family of sufficiently many disjoint unit spheres admits at most four different geometric permuations (for arbitrary disjoint spheres, the bound is Θ(nd−1)). By showing that it is impossible for four spheres to realize the two geometric permuations ABCD and BADC at the same time, we were able to improve this, showing that n ≥ 9 disjoint unit spheres admit at most two geometric permutations, which differ in the swapping of two adjacent spheres only [3]. (For 4 ≥ n ≥ 8, it is still open whether the correct answer is two or three.) The first Helly-type theorem for line transversals to spheres was proven by Holmsen et al. [4]. Their result is based on the following fact: Given a sequence of disjoint spheres in R, and consider all oriented lines intersecting all spheres in the given order. Then the set of orientations of these lines is a convex set (on the sphere of directions). Holmsen et al. proved this for disjoint unit spheres in R. We were able to generalize the result to unit spheres in arbitrary dimensions [2], and very recently Borcea et al. could generalize it to families of arbitrary disjoint spheres using algebraic techniques [1]. The convexity of the cone of directions appears to be a distinguishing feature of spheres—it does not even generalize to convex objects that are perfectly smooth and arbitrarily fat. It even appears that the convexity