Search

Given a family $$F$$F of $$n$$n pairwise disjoint compact convex sets in the plane with non-empty interiors, let $$d(F)$$d(F) denote the number of directions determined by the set of lines which are tangent to two or more sets of $$F$$F. Let $$d_n$$dn denote the minimum value of $$d(F)$$d(F) as this parameter ranges over all such families of size $$n$$n. We prove that $$d_n\ge n-1$$dn?n-1 for all $$n$$n and show that this bound is tight for $$n=6$$n=6, and nearly tight for $$n=3,4,5$$n=3,4,5. The proof utilizes allowable interval sequences.

In 2005, Goodman and Pollack introduced the concept of an allowable interval sequence, a combinatorial object which encodes properties of a family of pairwise disjoint convex sets in the plane. They, Dhandapani, and Holmsen used this concept to address Tverberg’s (1,k)-separation problem: How many pairwise disjoint compact convex sets in the plane are required to guarantee that one can be separated by a line from k others? (Denote this number by f k .) A new proof was provided that f 2=5, a result originally obtained by Tverberg himself, and the application of allowable interval sequences to the case of general k was left as an open problem. Hope and Katchalski, using other methods, proved in 1990 that 3k−1≤f k ≤12(k−1). In this paper, we apply the method of allowable interval sequences to give an upper bound on f k of under 7.2(k−1), shrinking the range given by Hope and Katchalski by more than half. For a family of translates we obtain a tighter upper bound of approximately 5.8(k−1).

Given a family F of n pairwise disjoint compact convex sets in the plane with non-empty interiors, let T(k) denote the property that every subfamily of F of size k has a line transversal, and T the property that the entire family has a line transversal. We illustrate the applicability of allowable interval sequences to problems involving line transversals in the plane by proving two new results and generalizing three old ones. Two of the old results are Klee’s assertion that if F is totally separated then T(3) implies T, and the following variation of Hadwiger’s Transversal Theorem proved by Wenger and (independently) Tverberg: If F is ordered and each four sets of F have some transversal which respects the order on F, then there is a transversal for all of F which respects this order. The third old result (a consequence of an observation made by Kramer) and the first of the new results (which partially settles a 2008 conjecture of Eckhoff) deal with fractional transversals and share the following general form: If F has property T(k) and meets certain other conditions, then there exists a transversal of some m sets in F, with k