TY - JOUR
T1 - Contraction and expansion of convex sets
AU - Langberg, Michael
AU - Schulman, Leonard J.
N1 - Funding Information:
Research supported in part by grants from the NSF and the NSA.
PY - 2009/10
Y1 - 2009/10
N2 - Let be a set system of convex sets in ℝd. Helly's theorem states that if all sets in 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 are not convex or if 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 is any family of convex sets in ℝd, then there is a finite subfamily S′ ⊆ S whose cardinality depends only on ε and d, such that {double intersection}CεS′C-ε ⊆ {double intersection}CεSC..The second result allows the sets in a limited type of nonconvexity:(b) If is a family of sets in ℝd, each of which is the union of kfat convex sets, then there is a finite subfamily S′ ⊆ S whose cardinality depends only on ε, d, and k, such that {double intersection}CεS′C-ε ⊆ {double intersection}CεSC..
AB - Let be a set system of convex sets in ℝd. Helly's theorem states that if all sets in 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 are not convex or if 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 is any family of convex sets in ℝd, then there is a finite subfamily S′ ⊆ S whose cardinality depends only on ε and d, such that {double intersection}CεS′C-ε ⊆ {double intersection}CεSC..The second result allows the sets in a limited type of nonconvexity:(b) If is a family of sets in ℝd, each of which is the union of kfat convex sets, then there is a finite subfamily S′ ⊆ S whose cardinality depends only on ε, d, and k, such that {double intersection}CεS′C-ε ⊆ {double intersection}CεSC..
KW - Helly-type theorems
KW - Nonconvex
UR - http://www.scopus.com/inward/record.url?scp=70350731126&partnerID=8YFLogxK
U2 - 10.1007/s00454-009-9214-y
DO - 10.1007/s00454-009-9214-y
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:70350731126
SN - 0179-5376
VL - 42
SP - 594
EP - 614
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 4
ER -