BOUNDING THE NUMBER OF GEOMETRIC PERMUTATIONS INDUCED BY K-TRANSVERSALS

Authors
GOODMAN JE POLLACK R WENGER R
Citation
Je. Goodman et al., BOUNDING THE NUMBER OF GEOMETRIC PERMUTATIONS INDUCED BY K-TRANSVERSALS, J COMB TH A, 75(2), 1996, pp. 187-197
Citations number
9
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
00973165 → ACNP
Volume
75
Issue
2
Year of publication
1996
Pages
187 - 197
Database
ISI
SICI code
0097-3165(1996)75:2<187:BTNOGP>2.0.ZU;2-A
Abstract
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)) differen t 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.