On neighbors in geometric permutations Academic Article uri icon

abstract

  • Abstract We introduce a new notion of 'neighbors' in geometric permutations. We conjecture that the maximum number of neighbors in a set S of n pairwise disjoint convex bodies in R d is O (n), and we prove this conjecture for d= 2. We show that if the set of pairs of neighbors in a set S is of size N, then S admits at most O (N d− 1) geometric permutations. Hence, we obtain an alternative proof of a linear upper bound on the number of geometric permutations for any finite family of pairwise disjoint convex bodies in the plane.

publication date

  • January 1, 2003