Shape sensitive geometric permutations
Y. Zhou, Subhash Suri · 2001
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 signicantly improves upon the (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 signi cant improvement on the O(n 2d 2 ) bound known for ...