Natan Rubin
Senior Academic
Improved bounds for geometric permutations
We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in Rd, for d = 3, is O(n2d-3 log n), improving Wenger's 20-year-old bound of O(n2d-2).
| Publication language | English |
| Pages | 367-390 |
| Journal | SIAM Journal on Computing |
| Volume | 41 |
| Issue number | 2 |
| Publication status | Published - 04.06.2012 |
Keywords
Combinatorial complexity
Convex sets
Geometric permutations
Line transversals
Lines in space
ASJC Scopus subject areas
General Computer Science
General Mathematics
