We prove that a set of  n  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 T( n   d -1 ) bound for the balls of arbitrary radii. Intrigued by this large gap between the two bounds, we also investigate how the number of geometric permutations varies as a function of shape, size, and spacing of objects. Our results include a tight bound of 2  d -1  on the geometric permutations of  n  disjoint rectangular boxes in  R d  , and a constant bound on the geometric permutations for disks in the plane when the ratio between the largest to smallest disks is bounded. An important consequence of the former theorem is that if the smallest bounding boxes containing a set of geometric objects in  R d   are pairwise disjoint, then those objects admit only 2  d -1  permutations, which is a significant improvement on the  O ( n  2 d -2 ) bound known for general convex objects.
['Yunhong Zhou', 'Subhash Suri']
Shape sensitive geometric permutations