A constant bound for geometric permutations of disjoint unit balls (Q1404497)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A constant bound for geometric permutations of disjoint unit balls |
scientific article |
Statements
A constant bound for geometric permutations of disjoint unit balls (English)
0 references
21 August 2003
0 references
An oriented line is called a line transversal for a set \(S\) of bodies in the \(d\)-dimensional euclidean space if it intersects every member of \(S\). If the objects in \(S\) are pairwise disjoint convex bodies, then a line transversal of \(S\) induces two linear orderings, which are the orders in which the line meets the members of \(S\). The two orders induced by a line transversal are essentially the same (one is the reverse of the other) and so they are together called a single geometric permutation. In the planar case the maximum number of geometric permutations of a family \(S\) with \(n\) members is known to be \(2n-2\). However for dimension \(d>2\) there is a big gap between the upper and the lower bound. This gap motivated to consider a natural specialized family of convex bodies: unit balls. The authors prove that the maximum number of geometric permutations for a family of \(n\) pairwise disjoint unit balls in the \(d\)-dimensional euclidean space is four, for \(n\) a sufficiently large constant that depends on the dimension \(d\).
0 references
line transversal
0 references
geometric permutation
0 references
combinatorial geometry
0 references