Improved Bounds for Geometric Permutations

Abstract

We show that the number of geometric permutations of an arbitrary collection of $n$ pairwise disjoint convex sets in ${\mathbb{R}}^d$, for $d\ge 3$, is $O(n^{2d-3}\log n)$, improving Wenger's 20 years old bound of $O(n^{2d-2})$.

A preliminary version accepted to FOCS 2010