Geometric permutations of higher dimensional spheres

摘要

In this paper, we prove that the maximum number of geometric permutations (induced by line transversals) of a set of n pairwise disjoint spheres with a bounded radius ratio in R~d for d ≥ 3 is at most 2~(2~(1/2)M+1), where M is the ratio of the largest radius and the smallest radius of the spheres. Setting M to 1, this gives an upper bound of 4 on the maximum number of geometric permutations for congruent spheres in R~d, matching a recently independently discovered result [Y. Zhou, S. Suri, in: Proc. of 12th Annual ACM-SIAM Symp. on Discrete Algorithms, 2001, pp. 234-243] on this case. Our result settles a conjecture in combinatorial geometry.