A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\) (Q5955145)

Let \({\mathcal O}\) be a set of \(n\) pairwise-disjoint convex \(\gamma\)-fat objects in~\({\mathbb{R}}^d\). Then the number of geometric permutations of~\({\mathcal O}\) is \(O(n^{d-1})\), the constant of proportionality being dependent on~\(d\) and~\(\gamma\). This result generalizes the bound \(\Theta(n^{d-1})\) obtained by \textit{S. Smorodinsky, J. S. B. Mitchell} and \textit{M. Sharir} [Discrete Comput. Geom. 23, 247-259 (2000; Zbl 0946.68145)]. Here a common transversal for a family \({\mathcal O}\) of \(n\) pairwise disjoint compact convex sets in \({\mathbb{R}}^ d\) is a line intersecting each set in~\({\mathcal O}\) which is done in a unique order, up to reversal. A~convex set \(O\subset {\mathbb{R}}^d\) is said to be \(\gamma\)-fat for some \(\gamma\geq 1\), if the ratio between the radius of the smallest ball containing~\(O\) and the radius of the largest ball contained in~\(O\) is at most~\(\gamma\).