Contraction and Expansion of Convex Sets |
| |
Authors: | Michael Langberg Leonard J Schulman |
| |
Institution: | (1) IBM T. J. Watson Research Center and MIT, 32-221, 1101 Kitchawan Road, Yorktown Heights, NY 10598, USA;(2) MIT Sloan School of Management, 50 Memorial Drive, Cambridge, MA 02139-4307, USA |
| |
Abstract: | 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: |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|