Geometric permutations of high dimensional spheres
Yingping Huang, Jinhui Xu, Danny Z. Chen · 2001
We prove the maximum number of geometric permutations, induced by line transversals to a set of n pairwise disjoint congruent spheres in R d with d 3, is no more than 4 when n is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of n noncongruent spheres of bounded radius ratio in R d , d 3, is at most 2 b p 2Mc+1 , where M is the ratio of the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry. 1 Overview Given a set A of objects in the Euclidean space R d , a line l is said to be a line transversal of A if l intersects every object o 2 A. For a set A of pairwise disjoint convex objects, a line transversal l defines two linear orders along l (from both directions) in which l meets the members of A. Since the two orders are essentially the same, with one being the reverse of the other, we count them as one geometric permutation. ...