The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2 (Q748891)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2 |
scientific article |
Statements
The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2 (English)
0 references
1990
0 references
A transversal of the family A of n convex, compact and pairwise disjoint sets \(\{a_ 1,...,a_ N\}\) in \({\mathbb{R}}^ 2\) is a line that intersects all sets of A. Each transversal intersects the elements of A in a unique order, up to reversal. This gives a pair of permutations of \(\{\) 1,2,...,n\(\}\), one being the reverse of the other; it is called a geometric permutation of A. An upper bound of \(6n+6\) on the number of geometric permutations of A has been obtained by R. Wenger (1986). In this paper the authors show, via a sequence of three lemmas (which deserve interest in themselves), that for \(n\geq 4\) the maximum number of geometric permutations for A is \(2n-2\) and that for \(n=1,2,3\) this maximum equals 1,1,3, respectively.
0 references
transversal
0 references
geometric permutation
0 references
maximum number
0 references
0 references