Contraction and Expansion of Convex Sets

摘要

Let S{mathcal{S}} be a set system of convex sets in ℝ d . Helly’s theorem states that if all sets in S{mathcal{S}} have empty intersection, then there is a subset S¢ Ì S{mathcal{S}}'subset{mathcal{S}} of size d+1 which also has empty intersection. The conclusion fails, of course, if the sets in S{mathcal{S}} are not convex or if S{mathcal{S}} does not have empty intersection. Nevertheless, in this work we present Helly-type theorems relevant to these cases with the aid of a new pair of operations, affine-invariant contraction, and expansion of convex sets. These operations generalize the simple scaling of centrally symmetric sets. The operations are continuous, i.e., for small ε>0, the contraction C −ε and the expansion C ε are close (in the Hausdorff distance) to C. We obtain two results. The first extends Helly’s theorem to the case of set systems with nonempty intersection: