Transversal Helly numbers, pinning theorems and projection of simplicial complexes

The efficient resolution of various problems in computational geometry, for instance visibility computation or shape approximation, raises new questions in line geometry, a classical area going back to the mid-19th century. This thesis fits into this theme, and studies Helly numbers of certain sets of lines, an index related to certain basis theorems arising in computational geometry and combinatorial optimization. Formally, the Helly number of a family of sets with empty intersection is the size of its largest inclusion-wise minimal sub-family with empty intersection. For $d\ge 2$ let $h_d$ denote the least integer such that for any family ${B_1, \ldots, B_n}$ of pairwise disjoint balls of equal radius in $R^d$, the Helly number of ${T(B_1), \ldots, T(B_n)}$ is at most $h_d$, where $T(B_i)$ denotes the set of lines intersecting $B_i$. In 1957, Ludwig Danzer showed that $h_2$ equals $5$ and conjectured that $h_d$ is finite for all $d \ge 2$ and increases with $d$. We establish that $h_d$ is at least $2d-1$ and at most $4d-1$ for any $d \ge 2$, proving the first conjecture and providing evidence in support of the second one. To study Danzer's conjectures, we introduce the pinning number, a local analogue of the Helly number that is related to grasping questions studied in robotics. We further show that pinning numbers can be bounded for sufficiently generic families of polyhedra or ovaloids in $R^3$, two situations where Helly numbers can be arbitrarily large. A theorem of Tverberg asserts that when ${B_1, \ldots, B_n}$ are disjoint translates of a convex figure in the plane, the Helly number of ${T(B_1), \ldots, T(B_n)}$ is at most $5$. Although quite different, both our and Tverberg's proofs use, in some way, that the intersection of at least two $T(B_i)$'s has a bounded number of connected components, each contractible. Using considerations on homology of projection of simplicial complexes and posets, we unify the two proofs and show that such topological condition suffice to ensure explicit bounds on Helly numbers.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00650204
Author Goaoc, Xavier
Maintainer CCSD
Last Updated May 19, 2026, 23:27 (UTC)
Created May 19, 2026, 23:27 (UTC)
Identifier tel-00650204
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Effective Geometric Algorithms for Surfaces and Visibility (VEGAS) ; INRIA Lorraine ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)
creator Goaoc, Xavier
date 2011-12-07T00:00:00
harvest_object_id 5ef5eeee-baae-4ac7-a035-60cdf507e31a
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-11-04T00:00:00
set_spec type:HDR