Bounding the Number of Geometric Permutations Induced byk-Transversals
Jacob Eli Goodman, Richard M. Pollack, Rephael Wenger · Journal of Combinatorial Theory Series A · 1996
We prove that a suitably separated family ofncompact convex sets inRdcan be met byk-flat transversals in at mostO(k)d2 ((2k+1−2k)(nk+1))k(d−k), or for fixedkandd,O(nk(k+1)(d−k)) different order types. This is the first non-trivial upper bound for 1 2.