Allowable Interval Sequences and Separating Convex Sets in the Plane

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 ₂=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).