Contraction and expansion of convex sets
type: Item
instance of: scholarly article
title: Contraction and expansion of convex sets
zbMATH Open document ID: 1204.52009
author: Michael Langberg
author: Leonard J. Schulman
published in: Discrete \& Computational Geometry
publication date: 2009-12-14T00:00:00Z
review text: The authors introduce two operations on convex sets, called contraction and expansion, that generalize scaling of centrally symmetric sets. The operations are defined for \(C\) convex and \(\varepsilon \geq -1\) using intersections of slabs. With the help of these new operations, the authors prove two Helly-type theorems: one for families of sets that have empty intersection, and one for families of sets in which the members are not convex sets of a certain limited type. More precisely, with \(C^\varepsilon\) being the expansion and \(C^{-\varepsilon}\) being the contraction of the convex set \(C\) with parameter \(\varepsilon\), they establish the following two statements. {\parindent6mm \begin{itemize}\item[(a)] If \({\mathcal S}\) is a family of convex sets in \({\mathbb R}^d\), then there is a finite subfamily \({\mathcal S}'\subseteq {\mathcal S}\) whose cardinality depends only on \(\varepsilon\) and \(d\), such that \(\bigcap_{C\in{\mathcal S}'}C^{-\varepsilon}\subseteq\bigcap_{C\in {\mathcal S}}C\). \end{itemize}} For a real number \(k\geq 1\), we call a convex set \(C\) \(k\)-fat, if the ratio of the radius of the circumsphere of \(C\) and the radius of the insphere of \(C\) is equal to \(k\). {\parindent6mm \begin{itemize}\item[(b)] If \({\mathcal S}\) is a family of sets in \({\mathbb R}^d\), each of which is the union of \(k\)-fat convex sets, then there is a finite subfamily \({\mathcal S}'\subseteq {\mathcal S}\) whose cardinality depends only on \(\varepsilon\), \(d\), and \(k\), such that \(\bigcap_{C\in{\mathcal S}'}C^{-\varepsilon}\subseteq\bigcap_{C\in {\mathcal S}}C\). \end{itemize}}
Mathematics Subject Classification ID: 52A35
Mathematics Subject Classification ID: 52A20
zbMATH DE Number: 5646270
zbMATH Keywords: Helly-type theorems
zbMATH Keywords: nonconvex
zbMATH Keywords: contraction
zbMATH Keywords: expansion
reviewed by: Ferenc Fodor
MaRDI profile type: Publication
full work available at URL: s00454-009-9214-y
OpenAlex ID: W2134453913
cites work: Bounding the piercing number
cites work: A short proof of an interesting Helly-type theorem
cites work: Quantitative Helly-Type Theorems
cites work: Q4790110
cites work: Helly-type theorems for approximate covering
cites work: Metric entropy of some classes of sets with differentiable boundaries
cites work: Q4274009
cites work: Dynamic data structures for fat objects and their applications
cites work: Clustering lines in high-dimensional space
cites work: Q4274007
cites work: On Components in Some Families of Sets
cites work: Q5791470
cites work: Leray numbers of projections and a topological Helly-type theorem
cites work: Helly type properties of unions of convex sets
cites work: A Helly-type theorem for unions of convex sets
cites work: Helly's Theorems on Convex Domains and Tchebycheff's Approximation Problem
cites work: Q5770072
cites work: The complexity of the free space for a robot moving amidst fat obstacles
cites work: Q4400994
DOI: 10.1007/S00454-009-9214-Y
description: scientific article; zbMATH DE number 5646270