Transversal Helly numbers, pinning theorems and projection of simplicial complexes

Nombres de Helly, théorèmes d'épinglement et projection de complexes simpliciaux

Xavier Goaoc (1)

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility

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.

La résolution efficace de certaines questions de géométrie algorithmique, par exemple les calculs de visibilité ou l'approximation de forme, soulève de nouvelles questions de géométrie des droites, domaine classique dont l'origine remonte à la seconde moitié du 19e siècle. Ce mémoire s'inscrit dans ce cadre, et étudie les nombres de Helly de certains ensembles de droites, un indice reliée à certains théorèmes de la base apparaissant en optimimisation combinatoire. Formellement, le nombre de Helly d'une famille d'ensembles d'intersection vide est le cardinal de sa plus petite sous-famille d'intersection vide et minimale pour l'inclusion relativement à cette propriété. En 1957, Ludwig Danzer a formulé la conjecture que pour tout $d \ge 2$ il existe une constante $h_d$ telle que pour toute famille $\{B_1, \ldots, B_n\}$ de boules deux à deux disjointes et de même rayon, le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $h_d$; ici, $T(B_i)$ désigne l'ensemble des droites coupant $B_i$. Danzer a, de plus, spéculé que la constante $h_d$ (minimale) croît strictement avec $d$. Nous prouvons que de telles constantes existent, et que $h_d$ est au moins $2d-1$ et au plus $4d-1$ pour tout $d \ge 2$. Cela prouve la première conjecture et étaye la seconde. Nous introduisons, pour étudier les conjectures de Danzer, un analogue local du nombre de Helly que nous appellons nombre d'épinglement et qui se rattache à la notion d'immobilisation étudiée en robotique. Nous montrons que le nombre d'épinglement est borné pour toute famille (suffisament générique) de polyèdres ou d'ovaloides de $R^3$, deux cas où les nombres de Helly peuvent être arbitrairement grands. Un théorème de Tverberg énonce que si $\{B_1, \ldots, B_n\}$ est une famille de convexes du plan disjoints et congruents par translation alors le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $5$. Quoique relativement différentes, notre preuve et celle de Tverberg exploitent toutes deux le fait que toute intersection d'au moins deux $T(B_i)$ a un nombre borné de composantes connexes, chacune contractile. Par des considérations sur l'homologie de projections de complexes et d'ensembles simpliciaux, nous unifions ces deux preuves et montrons que cette condition topologique suffit à établir une borne explicite sur le nombre de Helly.

Mots clés: Discrete and computational geometry; Line geometry; Helly's theorem

Mots clés: Géométrie algorithmique et combinatoire; Géométrie des droites; Théorème de Helly

Domaines: Géométrie algorithmique [cs.CG]; Mathématique discrète [cs.DM]

Xavier Goaoc. Transversal Helly numbers, pinning theorems and projection of simplicial complexes. Computational Geometry [cs.CG]. Université Henri Poincaré - Nancy I, 2011. ⟨tel-00650204v2⟩