A Helly-type theorem for unions of convex sets (Q1361809): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Ji{ří} Matoušek / rank | |||
Property / reviewed by | |||
Property / reviewed by: Robert J. MacG. Dawson / rank | |||
Property / author | |||
Property / author: Ji{ří} Matoušek / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Robert J. MacG. Dawson / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 04:04, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Helly-type theorem for unions of convex sets |
scientific article |
Statements
A Helly-type theorem for unions of convex sets (English)
0 references
28 July 1997
0 references
In this paper, it is shown that for every \(d,k\geq 1\), there exist numbers \(q(d,k)\) and \(h(d,k)\) such that any family \({\mathcal K}\) of subsets of \(\mathbb{R}^d\) for which the intersection of \(q\) or fewer elements of \({\mathcal K}\) is a union of at most \(k\) convex sets, has Helly number at most \(h\). (This result was proved, in a different way, by Alon and Kalai, in 1995.) A related ``topological Helly-type theorem'' is also proved. There is an interesting section on related results, in which connections to linear programming and to other topics in convexity theory are summarized. In the proof of the geometric theorem, the author first introduces a property, with a combinatorial flavor, that is satisfied by unions of at most \(k\) convex sets in \(\mathbb{R}^d\). It is then shown, using order-of-magnitude arguments, that if \({\mathcal K}\) is a family of sets in \(\mathbb{R}^d\), such that the intersection of any finite subfamily has this new property, it has a Helly number that is less than a certain bound. This bound can, in principle, be computed on the basis of the results in the paper, but is quite large and (according to the author) perhaps not the best possible.
0 references
Helly-type theorems
0 references
unions of convex sets
0 references
topological Helly-type theorems
0 references