## ملخص

Let S be a set system of convex sets in ℝ^{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 Hausdorff) to C. We obtain two results. The first extends Helly's theorem to the case of set systems with non-empty intersection: (a) If S 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 ∩_{C∈S}′C^{-ε} ⊆∩_{C∈S}C. The second result allows the sets in S a limited type of non-convexity: (b) If S is a family of sets in ℝ^{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∈S}C.

اللغة الأصلية | الإنجليزيّة |
---|---|

الصفحات | 25-28 |

عدد الصفحات | 4 |

حالة النشر | نُشِر - 2007 |

الحدث | 19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, كندا المدة: ٢٠ أغسطس ٢٠٠٧ → ٢٢ أغسطس ٢٠٠٧ |

### !!Conference

!!Conference | 19th Annual Canadian Conference on Computational Geometry, CCCG 2007 |
---|---|

الدولة/الإقليم | كندا |

المدينة | Ottawa, ON |

المدة | ٢٠/٠٨/٠٧ → ٢٢/٠٨/٠٧ |