Bounding the number of geometric permutations induced by k-transversals

We prove that a suitably separated family of n compact convex sets in R(d) can be met by k-flat transversals in at most O(k)(d2)(((2k+1-2)(k))((n)(k+1)))(k(d-k)), or for fixed k and d, O(n(k(k+1)(d-k)) different order types. This is the first non-trivial upper bound for 1 < k < d - 1, and generalizes (asymptotically) the best upper bounds known for line transversals in R, d > 2. (C) 1996 Academic Press, Inc.