On neighbors in geometric permutations. (Q1398279)

Let \(S\) be a family of disjoint convex bodies in \({\mathbb R}^d\). A line that intersects every member of \(S\) is called a line transversal of \(S\). Each line transversal \(\ell \) of \(S\) induces a pair of linear orderings of \(S\) by the order in which the members of \(S\) are met by \(\ell \) (one order being the reverse of the other). These pairs of orders are called geometric permutations of \(S\), and the subject of this paper is to find upper bounds for the number \(GP(S)\) of these permutations. To do this, the following notion is introduced. Two bodies \(a,b\in S\) are called neighbors if there exists a line transversal \(\ell \) of \(S\) such that \(a\) and \(b\) are consecutive elements of the geometric permutation induced by \(\ell \). The set of neighbor pairs in \(S\) is then denoted by \(N(S)\), and it turns out that \(GP(S)=O(\left| N(S)\right| ^{d-1})\). The main result says that \( \left| N(S)\right| =O(n)\) in the plane, which leads to a new proof of the known fact \(GP(S)=O(n)\) for \(d=2\). It is conjectured that \(\left| N(S)\right| =O(n)\) for all dimensions \(d\), which would imply the tight bound \(GP(S)=O(n^{d-1})\).