A Helly-Type Theorem for Unions of Convex Sets

We prove that for any d, k ≥ 1 there are numbers q = q(d,k) and h = h(d,k) such that the following holds: Let be a family of subsets of the d-dimensional Euclidean space, such that the intersection of any subfamily of consisting of at most q sets can be expressed as a union of at most k convex sets. Then the Helly number of is at most h. We also obtain topological generalizations of some cases of this result. The main result was independently obtained by Alon and Kalai, by a different method. Received April 14, 1995, and in revised form August 1, 1995.