Improved Bounds for Geometric Permutations

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in R d, for d ≥ 3, is O(n 2d-3 log n), improving Wenger's 20 years old bound of O(n 2d-2 ).

Authors

• Natan Rubin
• Haim Kaplan
• Micha Sharir

Keywords

• Face
• Upper bound
• Complexity theory
• Shape
• Polynomials
• Indexes
• Geometry
• Convex Set
• Collection Of Sets
• Number Of Permutations
• Loss Of Generality
• Transverse Sections
• Time Management
• Hyperplane
• Direct Line
• General Position
• Great Circle
• Three-dimensional Case
• Logarithmic Factor
• geometric permutations
• line transversals
• convex sets
• arrangements