A short proof of an interesting Helly-type theorem (Q1913693)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A short proof of an interesting Helly-type theorem |
scientific article |
Statements
A short proof of an interesting Helly-type theorem (English)
0 references
27 May 1996
0 references
Also interesting is the proof. The Helly-type theorem (first conjectured by Grünbaum and Motzkin) states: A family \(\mathcal F\) of sets in \(\mathbb{R}^d\) such that the intersection of every non-empty finite subfamily of \(\mathcal F\) can be expressed as the disjoint union of at most \(k\) closed convex sets has Helly number at most \(k(d+1)\). The minimization problem constructed by the author is computationally similar to linear programming, although geometrically the intersection of constraints fails not only to be convex but even to be connected. The method will probably find application to other problems. There is a fine bibliography and a well-written introduction and ``framework''.
0 references
Helly-type theorem
0 references
linear programming
0 references