Fact-checked by Grok 2 weeks ago

Helly's theorem

Helly's theorem is a cornerstone result in convex geometry that characterizes the intersection properties of convex sets in Euclidean space. In its classical form, the theorem states that for a finite collection of convex sets in \mathbb{R}^n, if every subcollection of at most n+1 sets has a nonempty intersection, then the intersection of all the sets in the collection is nonempty.^[1] This condition, known as the (n+1)-Helly property, ensures a global intersection point under the assumption of convexity, highlighting the dimensional bound inherent to Euclidean spaces.^[2] The theorem was discovered by the Austrian mathematician Eduard Helly in 1913. He was later interned as a prisoner of war during World War I, though he did not publish it immediately due to his circumstances.^[2] Helly communicated the result to Johann Radon, who provided the first published proof in 1921, utilizing Radon's own theorem on partitions of point sets into intersecting convex hulls.^[3] Helly himself published a proof in 1923, establishing the theorem formally in the literature.^[2] Helly's theorem forms part of a foundational trio in convex geometry alongside Carathéodory's theorem (1907), which bounds the number of points needed to express elements in a convex hull, and Radon's theorem (1921), which guarantees partitions of point sets with intersecting convex hulls; each can be derived from the others using techniques like hyperplane separation.^[2] The result has inspired extensive generalizations, including versions for j-dimensional intersections, abstract convexity spaces, and fractional or colorful variants that relax the intersection conditions while preserving probabilistic guarantees.^[1] Applications span optimization (e.g., solving systems of convex inequalities), combinatorial geometry (e.g., transversal and covering problems), and approximation theory (e.g., bounding diameters of intersections).^[2]

Historical Context

Discovery and Publication

Eduard Helly discovered the key ideas behind the theorem in 1913, during his early research on integral equations, where considerations of selections and intersections in functional analysis led to the geometric insight regarding convex sets. He communicated the result privately to Johann Radon around this time and presented it in a lecture to the Viennese Mathematical Association in 1913, though no formal proof was recorded then. The outbreak of World War I interrupted Helly's work; he served in the Austrian army, was wounded in 1915, captured, and held as a prisoner of war in Siberia until his release in 1920, during which he continued writing on integral equations but delayed publishing the theorem.^[4] Helly provided the first written proof in 1923, in his paper titled "Über Mengen konvexer Körper mit gemeinschaftlichen Punkten," published in the Jahresbericht der Deutschen Mathematiker-Vereinigung. By then, alternative proofs had appeared: Johann Radon published one in 1921 using his own eponymous theorem on convex sets as a precursor, while Dénes Kőnig offered another in 1922, connecting the result to intersection properties in infinite graphs. These early publications helped establish the theorem's significance in convex geometry before Helly's version reached print. The initial reception was positive among European mathematicians working in convexity and analysis, with Radon and Kőnig's contributions highlighting its broader applicability beyond Helly's original analytic context. Helly's 1923 proof, though concise at just two pages, solidified the result and influenced subsequent developments in the field.

Eduard Helly's Contributions

Eduard Helly was born on June 1, 1884, in Vienna, Austria, into a Jewish family; his father, Sigmund Helly, worked as a civil servant.^[4] He studied mathematics, physics, and philosophy at the University of Vienna from 1902 to 1907, earning his doctorate in 1907 under Wilhelm Wirtinger, followed by a year of advanced study at the University of Göttingen under David Hilbert, Felix Klein, Hermann Minkowski, and Carl Runge.^[5] After initial teaching roles at a Viennese gymnasium and private lessons, Helly served in the Austrian army during World War I, where he was wounded and imprisoned in Siberia until 1920. Upon returning to Vienna, he qualified as a Privatdozent at the university in 1921 while working as an actuary at a bank and later at the Phönix life insurance company. Due to the Nazi annexation of Austria in 1938 and antisemitic persecution, Helly emigrated to the United States that September, securing positions at small colleges in New Jersey before becoming a visiting lecturer at the Illinois Institute of Technology in Chicago, where he died of heart failure on November 28, 1943.^[4]^[5] Helly's early mathematical career centered on functional analysis, with his 1912 habilitation thesis, "Beiträge zur Theorie der Fredholmschen Integralgleichung," addressing integral equations and laying groundwork for concepts in normed spaces and the uniform boundedness principle.^[4] This work introduced his selection principle, later known as Helly's selection theorem, which asserts that a uniformly bounded sequence of monotone real functions on a closed interval admits a pointwise convergent subsequence, relying on compactness arguments in the space of bounded variation functions.^[4] The ideas from this thesis directly inspired his 1913 discovery of the intersection theorem for convex sets, marking a pivotal shift in his research toward geometry, though it remained unpublished until 1923. Subsequent contributions included a 1921 paper on systems of linear equations with infinitely many unknowns, advancing infinite-dimensional analysis, and explorations in orthogonal expansions and convergence criteria in his 1912 work "Über Reihenentwicklungen."^[6]^[5] In later years, Helly extended his analytical expertise to topology, notably in a 1930 paper on systems of closed sets with common points, generalizing intersection properties beyond convexity. These efforts bridged functional analysis and geometric structures, influencing the development of convexity theory through compactness and selection principles. Helly's theorem on convex sets intersections stands as the cornerstone of his legacy, exemplifying his transition from integral equations and bounded variation in analysis to foundational results in convex geometry.^[5]^[6]

Statement of the Theorem

Finite Families

Helly's theorem in its finite form states that if \mathcal{F} is a finite family of convex sets in \mathbb{R}^d with |\mathcal{F}| \geq d+1, and every subfamily of d+1 sets from \mathcal{F} has nonempty intersection, then \bigcap_{K \in \mathcal{F}} K \neq \emptyset.^[2] The minimal integer h such that the intersection condition on subfamilies of size at most h implies the full intersection is called the Helly number of the family of convex sets in \mathbb{R}^d, and it equals d+1.^[2] This bound is sharp, as demonstrated by a family of d+1 closed half-spaces in \mathbb{R}^d whose bounding hyperplanes are in general position forming the facets of a simplex; every d of these half-spaces intersect nonemptily (in an unbounded convex region), but the full intersection is empty.^[2] The theorem requires the sets to be convex; without this assumption, it fails even for finite families. For instance, there exist finite families of non-convex sets in \mathbb{R}^d where every d+1 intersect nonemptily, but the entire family does not, and the Helly number can be arbitrarily large. The sets are typically taken to be closed, though the result holds more generally for arbitrary convex sets in the finite case.^[2] A basic illustration occurs in \mathbb{R}^2, where the theorem asserts that if every three convex sets in a finite family of at least three have nonempty intersection, then the whole family does. To see the sharpness, consider three lines forming the sides of a triangle: every pair intersects at a vertex, but all three have empty common intersection.^[2] This finite version of the theorem was discovered by Eduard Helly in 1913.^[2]

Infinite Families

Helly's theorem extends naturally to infinite families of convex sets in \mathbb{R}^d, but requires the sets to be compact to ensure the conclusion holds. Specifically, if \mathcal{F} is an arbitrary infinite family of compact convex sets in \mathbb{R}^d such that every finite subfamily consisting of at most d+1 sets has nonempty intersection, then the intersection of all sets in \mathcal{F} is nonempty.^[7] This version parallels the finite case but leverages the topological properties of compact sets to handle the infinite collection.^[2] Compactness is essential for the theorem to apply to infinite families, as non-compact convex sets can lead to failures even when the finite intersection condition is satisfied. Without compactness—meaning the sets need not be closed and bounded—counterexamples abound where every finite subcollection of size at most d+1 intersects, but the entire family does not. For instance, in \mathbb{R}^1, consider the family of closed half-lines [n, \infty) for n = 1, 2, \dots; any finite subcollection intersects at a point beyond the maximum starting index, yet the infinite intersection is empty since no point lies in all half-lines simultaneously.^[7] Similarly, in \mathbb{R}^2, the family of closed upper half-planes \{(x, y) \in \mathbb{R}^2 \mid y \geq n\} for n = 1, 2, \dots has every finite subcollection (including any three) intersecting in a half-plane at sufficiently large y, but the total intersection is empty.^[8] These examples highlight how unboundedness allows intersections to "escape to infinity," evading a global common point. Under compactness, the infinite version of Helly's theorem equates to the finite case through the finite intersection property: if every finite subfamily intersects, then the whole family does for compact convex sets, and the d+1 condition ensures this property holds for all finite subcollections via the finite theorem.^[2] Thus, compactness bridges the gap, guaranteeing that no infinite family satisfying the local intersection condition diverges to an empty global intersection.^[7]

Proof

Prerequisites: Radon's Theorem

Radon's theorem, a fundamental result in convex geometry, states that for any finite set of d+2 points in \mathbb{R}^d, there exists a partition of the set into two disjoint subsets such that the convex hulls of these subsets intersect.^[9] This theorem was introduced by Johann Radon in his 1921 paper on collections of convex bodies sharing a common point, where it served as a key lemma in establishing a proof of Helly's theorem.^[9] The result provides an essential intersection guarantee for minimal configurations of affinely dependent points, which is crucial in the inductive step of the standard proof of Helly's theorem for finite families of convex sets in \mathbb{R}^d.^[8] Specifically, when considering more than d+1 convex sets whose every d+1 subsets intersect, one selects a point from each set (omitting one per selection), yielding d+2 or more affinely dependent points; Radon's theorem then partitions these points into subsets with intersecting convex hulls, ensuring a common intersection point for all sets.^[8] A simple illustration occurs in \mathbb{R}^1, where any three points on the real line—say a < b < c—can be partitioned into the subsets \{a, c\} and \{b\}, whose convex hulls (the intervals [a, c] and $$) intersect at b. This captures the theorem's essence in the lowest dimension, highlighting the unavoidable overlap in convex hulls for d+2 points.

Proof Outline

The proof of Helly's theorem for finite families of convex sets in \mathbb{R}^d is established by induction on the number of sets n.^[9] For the base case n = d+1, the hypothesis states that the intersection of any d+1 sets is nonempty, which directly implies that the intersection of the entire family is nonempty.^[9] For the inductive step with n > d+1, assume the result holds for all smaller families satisfying the Helly condition (every d+1 sets intersect). Consider a family \{K_1, \dots, K_n\} of convex sets where every d+1 have nonempty intersection. For each i, the subfamily \{K_j : j \neq i\} has n-1 < n sets, satisfies the Helly condition as a subfamily of the original, and thus has nonempty intersection C_i = \bigcap_{j \neq i} K_j by the inductive hypothesis; each C_i is convex.^[9] Select points x_i \in C_i for i = 1, \dots, n, forming the set X = \{x_1, \dots, x_n\} with |X| = n \geq d+2. By Radon's theorem, X admits a partition into disjoint subsets S and T such that \operatorname{conv}(S) \cap \operatorname{conv}(T) \neq \emptyset; let p \in \operatorname{conv}(S) \cap \operatorname{conv}(T).^[9] To show p \in \bigcap_{k=1}^n K_k, fix any k. Each x_i \in C_i \subset K_k for all i \neq k. If x_k \in T, then every point in S has index i \neq k, so S \subset K_k and \operatorname{conv}(S) \subset K_k by convexity of K_k, hence p \in K_k; the case x_k \in S follows symmetrically using T \subset K_k. Thus, p lies in the total intersection, completing the induction.^[9] For infinite families of compact convex sets in \mathbb{R}^d where every d+1 have nonempty intersection, the finite case implies every finite subfamily intersects. The family thus possesses the finite intersection property, and since the sets are compact, the compactness of \mathbb{R}^d (via the Heine-Borel theorem) ensures the total intersection is nonempty.^[10]

Variants

Colorful Helly Theorem

The colorful Helly theorem is a generalization of Helly's theorem to multiple families of convex sets, often referred to as a "rainbow" or transversal version. Specifically, let \mathcal{F}_1, \mathcal{F}_2, \dots, \mathcal{F}_{d+1} be finite families of convex sets in \mathbb{R}^d. If every transversal selection—one set from each family—has nonempty intersection, then there exists some i such that the entire family \mathcal{F}_i has nonempty intersection.^[11] This result recovers the original Helly theorem as the special case where all families coincide. The theorem was first observed by László Lovász in the 1970s, though his proof remained unpublished; the first published proof appeared in a 1982 paper by Imre Bárány, who framed it within a broader generalization of Carathéodory's theorem.^[11] Gil Kalai popularized and extended the result in the 1980s through work on topological and matroidal variants, including connections to simplicial complexes. More recent developments, such as those in 2019, have explored colorful extensions in abstract convexity spaces and links to fractional versions, including proofs via bounded Radon numbers. Recent work as of 2025 has introduced quantitative colorful Helly theorems for discrete boxes and other structured families.^[12] A standard proof reduces the colorful case to the classical Helly theorem using auxiliary constructions. One approach, due to Lovász and detailed in later works, involves assuming all families have empty total intersection and deriving a contradiction by constructing a larger auxiliary family whose (d+1)-tuples fail to intersect, violating the hypothesis; this often employs adding a universal set encompassing all others to one family and applying a dual colorful Carathéodory result.^[11]^[13] For an example in \mathbb{R}^2, consider three families \mathcal{F}_1, \mathcal{F}_2, \mathcal{F}_3 of line segments (colored red, blue, and green, respectively). If every rainbow triple—one segment from each color—intersects at a common point, then at least one color class, say all red segments, must have a nonempty total intersection. This illustrates the theorem's utility in combinatorial geometry, such as piercing problems for colored objects.^[11]

Fractional Helly Theorem

The fractional Helly theorem provides a quantitative measure of intersection patterns for finite families of convex sets in \mathbb{R}^d, relaxing the deterministic condition of Helly's theorem to probabilistic fractions. Specifically, let \mathcal{F} be a finite family of n convex sets in \mathbb{R}^d. If at least an \alpha-fraction of the (d+1)-tuples from \mathcal{F} have nonempty intersection, then there exists a subfamily \mathcal{G} \subseteq \mathcal{F} of size at least \beta n such that \bigcap_{K \in \mathcal{G}} K \neq \emptyset, where

\beta = 1 - (1 - \alpha)^{1/(d+1)}.

This bound is sharp and holds for any \alpha \in (0,1]. The theorem was first established by Katchalski and Liu in 1979, who proved the existence of such a subfamily but with a weaker dependence on \alpha and d. The optimal bound was independently obtained by Eckhoff and Kalai around 1984, resolving the quantitative sharpness. For \alpha = 1, the bound recovers \beta = 1, aligning with the classical Helly theorem. Setting \alpha = 1/(d+1) yields \beta > 0 depending on d, ensuring a positive fraction of the family intersects even under modest local intersection assumptions.^[14] This result bridges combinatorial geometry with probabilistic methods by quantifying how local tuple intersections imply global subfamily intersections, rather than requiring uniform conditions across all tuples. It has implications for analyzing random geometric configurations, such as families derived from random point sets, where fractional guarantees help assess the expected size of large intersecting substructures based on pairwise or small-tuple overlap probabilities. Recent developments, including a 2019 extension by Holmsen and Lee to convexity spaces with bounded Radon number, have generalized the theorem beyond Euclidean convexity while preserving the fractional structure. Further advancements as of 2022 include quantitative versions bounding the volume of intersections in fractional Helly theorems.^[15]

Generalizations

Hadwiger-Debrunner Theorem

The Hadwiger–Debrunner theorem generalizes Helly's theorem to families of compact convex sets in \mathbb{R}^d that satisfy a relaxed intersection condition known as the (p, q)-property, where p ≥ q ≥ d+1: among any p sets, some q have nonempty common intersection. The theorem states that any such family has a finite piercing number at most the Hadwiger–Debrunner number HD_d(p, q). For the special case q = d+1 and p = k > d+1, this means that in every collection of k sets, some d+1 have nonempty intersection, and the piercing number is bounded by (k-1)^d or similar functions derived from subsequent analyses.^[16] The theorem was proposed by Hugo Hadwiger and Hans Debrunner in their 1957 paper, where they proved the result for parameters satisfying p(d-1) < d(q-1) with the tight piercing bound p - q + 1, and conjectured the general case; this strengthened Helly's theorem by providing quantitative bounds on the minimal number of piercing points under weaker conditions. The full conjecture was resolved affirmatively by Noga Alon and Daniel J. Kleitman in 1992, confirming finite HD_d(p, q) for all p ≥ q ≥ d+1.^[16] When k = d+1, the condition reduces to every d+1 sets having nonempty intersection, which by Helly's theorem implies the entire family intersects, yielding piercing number 1.

Extensions to Abstract Convexity

Helly's theorem, originally formulated for convex sets in Euclidean space, extends to abstract convexity structures where the notion of convexity is generalized beyond vector spaces. In an abstract convexity space (X, \mathcal{C}), the family \mathcal{C} consists of convex sets satisfying properties such as containing singletons, the whole space X, and being closed under arbitrary intersections, allowing the study of intersection theorems in diverse settings like graphs, posets, and metric spaces. These spaces often admit Helly-type theorems when they possess a bounded Radon number, meaning that any family of convex sets with pairwise nonempty intersections can be partitioned into a fixed number of subfamilies each with nonempty total intersection, implying the colorful Helly property.^[17] A prominent example arises in graph theory with the clique Helly property, where the family of maximal cliques in a graph satisfies the Helly condition: if every pair of cliques intersects, then the entire family has a common vertex. Graphs exhibiting this property for chordless path convexity have a Helly number equal to the size of the largest clique, generalizing the intersection behavior to combinatorial structures.^[18] In partially ordered sets (posets) and lattices, the Helly number for convex sets—defined via order ideals or upset families—provides an analog to dimension. Doignon's theorem establishes that in the d-dimensional integer lattice \mathbb{Z}^d, the Helly number is $2^d, bounding the size of subfamilies needed to guarantee a common lattice point in the intersection.^[19] Recent work on exponential lattices \{\alpha^n : n \in \mathbb{N}_0\}^d for \alpha > 1 confirms finite Helly numbers, with exact values determined for specific dimensions and growth rates, highlighting boundedness tied to lattice "dimension."^[20] In metric spaces equipped with geodesic convexity—where convex sets are those containing shortest paths between points—Helly's theorem holds for families of convex sets in uniquely geodesic spaces, such as CAT(0) spaces, without requiring openness or closedness, as every finite subfamily with pairwise intersections has a total intersection.^[21] This extends the prototype from Euclidean convexity to broader metric geometries, preserving the Helly number at d+1 in d-dimensional analogs. Post-2000 developments, including surveys on combinatorial convexity, have explored Tverberg-type extensions in these spaces, where partitions into simplices with intersecting images generalize Radon partitions, often yielding bounded numbers in abstract settings with finite Radon numbers.^[22]^[23]

Applications

Combinatorial Geometry

Helly's theorem and its variants underpin several key results in combinatorial geometry, where they help analyze intersection properties of discrete geometric configurations such as point sets, convex objects, and visibility graphs. These applications often leverage the theorem's Helly number to bound the complexity of piercing, partitioning, or guarding problems, providing tight guarantees on the minimal structures needed to ensure global intersections or coverings. In transversal theory, Helly-type theorems establish bounds on piercing numbers for families of convex sets like disks and intervals, determining the minimal number of points or lines needed to intersect all members. For pairwise disjoint unit disks in the plane, if every five disks admit a common line transversal, then the entire family does, yielding a Helly number of 5 for this transversal property.^[22] In higher dimensions, for families of more than $4d-1 disjoint unit balls in \mathbb{R}^d, if every subfamily of size $4d-1 has a line transversal, the whole family admits one, establishing a Helly number of $4d-1.^[24] For intervals on the real line, Helly-Gallai type theorems further bound piercing numbers; specifically, for a finite family of closed intervals, if every k+1 intervals have piercing number at most m, then the entire family has piercing number at most a function of k and m, often linear in the parameters.^[25] Helly's theorem also implies results on Tverberg partitions of point sets, where the goal is to divide points into subsets whose convex hulls share a common point. In the proof of Tverberg's theorem, for a set of (r-1)(d+1)+1 points in \mathbb{R}^d, Helly's theorem is applied to the convex hulls of d+1-tuples to guarantee an intersection point, enabling the partition into r subsets with intersecting hulls.^[26] This extends to colorful variants: the colorful Helly theorem ensures that, for d+1 families of convex sets in \mathbb{R}^d, if every colorful selection of one set from each family intersects, then one family has nonempty intersection, directly implying colorful Tverberg partitions of multicolored point sets into rainbow subsets with intersecting convex hulls.^[27] In art gallery problems, Helly-type theorems characterize visibility in polygons by bounding the number of guards required to cover all vertices or points. For a planar polygon with h holes, if every p points include a triple visible from a single guard point, then the polygon can be guarded by O(h \cdot p) guards, drawing on Helly numbers to ensure global visibility from local conditions.^[28] More precisely, Berge's Helly-type theorem, which replaces intersection with convex union conditions, applies to visibility graphs: in \mathbb{R}^d, if every d+1 points in a compact set are visible from a common point (i.e., the set is star-shaped from that point), then the entire set is star-shaped, establishing a Helly number of d+1 for visibility.^[29] Recent surveys underscore Helly's role in computational geometry for set systems with finite Helly numbers, such as those arising in geometric transversals and partitions, enabling algorithms that sample small subfamilies to approximate global intersection properties efficiently.^[27] For instance, in random geometric settings, the fractional Helly theorem provides probabilistic bounds on intersection sizes, ensuring that if a positive fraction of small subfamilies intersect, a large subfamily does with high probability.^[28]

Optimization and Linear Programming

Helly's theorem plays a crucial role in determining the feasibility of linear programs (LPs) by reducing the verification of infinite constraint systems to finite checks. In \mathbb{R}^d, an LP is defined by a finite collection of half-spaces, each representing a linear inequality, and feasibility requires their intersection to be non-empty. Since half-spaces are convex sets, Helly's theorem implies that if every subset of d+1 half-spaces has a non-empty intersection, then the entire family does as well.^[30] This allows for efficient algorithmic verification: instead of checking all possible combinations, one can focus on subsets of size at most d+1, providing a combinatorial certificate of feasibility or infeasibility when a violating subset is found.^[31] In the broader context of generalized linear programming (GLP), Helly's theorem extends to abstract optimization frameworks that generalize standard LPs. A GLP is specified by a set of constraints H and an objective function w satisfying monotonicity (adding constraints cannot improve the objective) and locality (nearby bases yield similar objectives), with a combinatorial dimension d. Seminal work by Amenta established that every GLP admits a Helly-type property: the optimal value w(H) \leq m if and only if w(B) \leq m for every basis B \subseteq H of size at most d+1.^[30] This connection, developed in Amenta's 1994 thesis, enables linear-time expected algorithms for solving GLPs, such as those involving geometric constraints in higher dimensions.^[32] Applications of Helly's theorem in optimization include facility location problems, where it facilitates solving minimax objectives over convex regions. For instance, in the 1-center problem, finding the smallest disk covering a set of points in the plane reduces to checking intersections of disks centered at candidate points; Helly's theorem (with Helly number 3 in \mathbb{R}^2) ensures that if every triple intersects, a global center exists, leading to efficient prune-and-search algorithms.^[31] Similarly, in constraint satisfaction problems, Helly provides intersection certificates: a finite subset of d+1 constraints whose empty intersection certifies overall infeasibility, useful in geometric programming for verifying solution existence without exhaustive search.^[30] A representative example arises in optimizing over polyhedra in \mathbb{R}^d. Consider maximizing a linear objective over the intersection of half-spaces defining a polyhedron; Helly's theorem allows verification of non-emptiness by testing facets in subsets of size d+1, enabling incremental optimization algorithms that pivot on local bases to find global optima.^[31] The Hadwiger-Debrunner theorem, a generalization bounding the piercing number, briefly extends this to optimization with bounded facility placements.^[30]

References

[1]
[PDF] Helly's Theorem and its Equivalences via Convex Analysis
Helly's theorem is an important result from Convex Geometry. It gives sufficient conditions for a family of convex sets to have a nonempty intersection.
[2]
[PDF] helly's theorem and its relatives1 - Academic Web
His famous theorem on the intersection of convex sets (also commonly called "Helly's theorem") was discovered by him in 1913 and communicated to Radon. Helly ...
[3]
https://homepages.math.uic.edu/~suk/helly.pdf
[4]
Eduard Helly (1884 - 1943) - Biography - MacTutor
He studied at the University of Vienna and was awarded his doctorate in 1907 after writing a thesis under the direction of Wirtinger and Mertens. His thesis was ...
[5]
Helly, Eduard | Encyclopedia.com
In 1913 Helly presented his intersection theorem in a VMA lecture. Further projects he had announced were put aside with the outbreak of World War 1. Helly ...
[6]
None
Summary of each segment:
[7]
Eduard Helly (1884–1943), in memoriam | Results in Mathematics
Apr 18, 2013 · Article. Eduard Helly (1884–1943), in memoriam. Research papers; Published: 18 April 2013. Volume 7, pages 145–153, (1984); Cite this article.Missing: title | Show results with:title
[8]
[PDF] Helly's theorem
The first nontrivial case states that if every 3 among 4 convex sets in the plane intersect, then there is a point common to all 4 sets. This can be proved by ...
[9]
[PDF] Helly's Theorem with Applications in Combinatorial Geometry
Aug 31, 2016 · Helly was wounded in WWI and was prisoner of the Russians. He wrote about functional analysis from prison. Though discovered in 1913, the ...<|control11|><|separator|>
[10]
Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten
Cite this article. Radon, J. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Math. Ann. 83, 113–115 (1921). https://doi.org/10.1007/BF01464231.
[11]
[PDF] 1.3 Radon's Lemma and Helly's Theorem
An infinite version of Helly's theorem. If we have an infinite collection of convex sets in R such that any d+1 of them have a common point, the entire ...
[12]
https://arxiv.org/abs/2509.13115
[13]
[PDF] very colorful theorems - Instituto de Matemáticas, UNAM
A prominent role in combinatorial geometry is played by Helly's theorem which states that a finite family of convex sets in Rd has a non-empty intersection if ...<|control11|><|separator|>
[14]
a the end of §3. - American Mathematical Society
Volume 75, Number 2, July 1979. A PROBLEM OF GEOMETRY IN R". M. KATCHALSKI AND A. LIU. Abstract. Let 9 be a finite family of at least n + 1 convex sets in the.
[15]
Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem
The (p, q) property means among any p members of a set family, some q have a nonempty intersection. This settles an old problem of Hadwiger and Debrunner.Missing: original paper
[16]
[1512.04026] Improved bounds on the Hadwiger-Debrunner numbers
Dec 13, 2015 · The latter is the first near tight estimate of HD_d(p,q) for an extended range of values of (p,q) since the 1957 Hadwiger-Debrunner theorem. We ...Missing: statement | Show results with:statement
[17]
[2408.05871] Helly type problems in convexity spaces - arXiv
Aug 11, 2024 · Abstract:We report on some recent progress regarding combinatorial properties in convexity spaces with a bounded Radon number.Missing: geometries | Show results with:geometries
[18]
https://doi.org/10.1016/0012-365X(84)90021-9
[19]
On Helly Numbers of Exponential Lattices - DROPS
Jun 9, 2023 · This article is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 ...
[20]
[1401.6654] On Helly's theorem in geodesic spaces - arXiv
Jan 26, 2014 · In this short note we show that Helly's Intersection Theorem holds for convex sets in uniquely geodesic spaces (in particular in CAT(0) spaces)
[21]
[PDF] 4 HELLY-TYPE THEOREMS AND GEOMETRIC TRANSVERSALS
Jul 16, 2017 · The basic idea is that if C is a family of sets with a bounded Helly-number, and F is a finite family of sets such that the intersection of any ...
[22]
[PDF] Helly-type Problems - Gil Kalai
Aug 5, 2021 · This paper describes the fascinating area of Helly-type theorems, and ex- plains some of its main themes and goals through a large and colorful ...Missing: 1983 | Show results with:1983
[23]
[PDF] Helly-Type Theorems for Line Transversals to Disjoint Unit Balls
Feb 6, 2007 · Our aim is to apply the Topological Helly Theorem to sets of line transversals to pairwise-inflatable balls. Unfortunately, such sets are ...Missing: applications piercing disks intervals
[24]
About the piercing number of a family of intervals - ScienceDirect.com
Dec 6, 2015 · In this paper, we develop a Helly–Gallai type theorem for piercing number on finite families of closed intervals in , as well as some bounds for the piercing ...Missing: applications disks
[25]
[PDF] T Tverberg partition Tverberg point. The following
Therefore, by Helly's theorem, the convex hulls of all s-tuples have a common point x (typically not in A anymore). By Carathedory's theorem, x is contained in ...
[26]
http://homepages.math.uic.edu/~suk/tverberg.pdf
[27]
[PDF] Berge's theorem, fractional Helly, and art galleries
Abstract. In one of his early papers Claude Berge proved a Helly-type theorem, which replaces the usual “nonempty intersection” condition.
[28]
Berge's theorem, fractional Helly, and art galleries - ScienceDirect.com
In one of his early papers Claude Berge proved a Helly-type theorem, which replaces the usual “nonempty intersection” condition with a “convex union” ...
[29]
[PDF] Helly Theorems and Generalized Linear Programming
We use these results to explore the class GLP and show new applications to geometric optimization, and also to prove Helly theorems. In general, a GLP is a set ...
[30]
[PDF] Algorithmic Techniques for Geometric Optimization*
A typical facility location problem is: Given a set D of n demand points in ... known example of a Helly-type theorem is Helly's theorem itself [60], which.<|control11|><|separator|>
[31]
Helly theorems and generalized linear programming
We give many applications, including linear expected time algorithms for finding line transversals and hyperplane fitting in convex metrics. These include GLP ...