Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2009 | public
Journal Article

Contraction and Expansion of Convex Sets


Let S be a set system of convex sets in R^d . Helly's theorem states that if all sets in S have empty intersection, then there is a subset S' ⊂ S of size d+1 which also has empty intersection. The conclusion fails, of course, if the sets in S are not convex or if 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: (a) If S is any family of convex sets in R^d , then there is a finite subfamily S' ⊆ S whose cardinality depends only on ε and d, such that ⋂_(C∈S')C^(−ε)⊆⋂_(C∈S)C. The second result allows the sets in S a limited type of nonconvexity: (b) If S is a family of sets in R^d, each of which is the union of k fat convex sets, then there is a finite subfamily S' ⊆ S whose cardinality depends only on ε, d, and k, such that ⋂_(C∈S')C^(−ε)⊆⋂_(C∈S)C.

Additional Information

© 2009 Springer. Received: 5 October 2007; revised: 15 April 2009; accepted: 17 July 2009; published online: 4 August 2009. Research supported in part by grants from the NSF and the NSA. We would like to thank Jie Gao for several helpful discussions which led to the study of contraction and expansion of convex sets. We would also like to thank Gil Kalai, Micha Perles, and Jiri Matoušek for helpful discussions about this work. Finally, we would like to thank Micha Sharir for pointing out the work of Dudley [6].

Additional details

August 21, 2023
October 19, 2023