Disjoint Unit Spheres Admit at most Two Line Transversals

Otfried Cheong (INF), joint work with Xavier Goaoc and Hyeon-Suk Na

A line l is a line transversal for a set S of pairwise disjoint convex bodies in d-dimensional space if it intersects each element of S. A line transversal defines two linear orders on S (one the reverse of each other). Together, they are called a geometric permutation of S. Bounds on the number of geometric permutations of n disjoint convex bodies were established in the early 1990s. In 2-D, a tight bound of 2n-2 is known. In higher dimension, the bound is \Omega(n^{d-1}) and O(n^{2d-2}). For the special case of spheres, the gap can be closed, and the bound is O(n^{d-1}). We are interested in the even more special case of congruent spheres. It was known that congruent spheres admit at most four different geometric permutations, if n is large enough. We show that there can be at most two different geometric permutations, if n is large enough, and they differ by swapping a single pair of adjacent spheres in the order.

back to TU/e Combinatorial Theory Seminar announcements