Geometric transversal theory

A theory having its origin in a beautiful theorem of E. Helly in combinatorial geometry and a provocative question by P. Vincensini whose answer turned out to be negative.

Helly's theorem states [a14]: If $\mathcal{A}$ is a collection of compact convex sets in $\mathbf{R} ^ { d }$, every $d + 1$ or fewer members of which have a point in common, then there is a point common to all the members of $\mathcal{A}$.

A $k$-transversal to a collection of sets is a $k$-flat (cf. Higher-dimensional geometry) that meets every set in the collection. With this notion Helly's theorem can be reformulated to assert that if every $d + 1$ or fewer members of $\mathcal{A}$ have a $0$-transversal, then $\mathcal{A}$ has a $0$-transversal. In 1935, Vincensini [a17] asked whether there was a corresponding theorem for $k$-transversals to a collection of convex sets in $\mathbf{R} ^ { d }$: Does there exist an $r = r ( k , d )$ such that for every collection $\mathcal{A}$ of compact convex sets in $\mathbf{R} ^ { d }$, if every subcollection of at most $r$ members of $\mathcal{A}$ has a $k$-transversal, then $\mathcal{A}$ has a $k$-transversal?

Vincensini gave an incorrect proof that $r ( 1,2 ) = 6$. Subsequently, several examples showed that no finite $r ( 1,2 )$ exists, even if it is assumed that the sets of $\mathcal{A}$ are pairwise disjoint. It is perhaps counterintuitive that the existence of such a number should depend on whether the sets are pairwise disjoint; however, L. Danzer [a4] pointed out that although families of disjoint unit discs in the plane admit such a number (see below), there are examples, with $m$ arbitrarily large, of $m + 1$ unit discs in the plane (not disjoint) that do not have a line transversal even though any $m$ of them do. He also gave examples of $m + 1$ disjoint unit balls in $\mathbf{R} ^ { 3 }$ that have no plane transversal even though any $m$ of them do, for $m$ arbitrarily large.

With hopes dashed for a generalization of Helly's theorem in the form proposed by Vincensini, other Helly-type transversal theorems were found, where the elements of the collection $\mathcal{A}$ were subject to significant restrictions on either their shape or their relative position. Some noteworthy examples of such theorems are as follows.

Santaló's theorem.

([a15]) Let $\mathcal{A}$ be a collection of parallel rectangles in $\mathbf{R} ^ { 2 }$. If every $6$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ admits a line transversal. The number $6$ cannot be reduced in general.

This generalizes in two directions to:

a) Let $\mathcal{A}$ be a collection of parallelotopes in $\mathbf{R} ^ { d }$ with edges parallel to the coordinate axes. If every $2 ^ { d - 1 } ( 2 d - 1 )$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ admits a line transversal.

b) Let $\mathcal{A}$ be a collection of parallelotopes in $\mathbf{R} ^ { d }$ with edges parallel to the coordinate axes. If every $2 ^ { d - 1 } ( d + 1 )$ or fewer elements of $\mathcal{A}$ admit a hyperplane transversal, then $\mathcal{A}$ admits a hyperplane transversal.

Hadwiger's theorem.

([a11], [a5]) Suppose $\mathcal{A}$ is a collection of compact convex sets in $\mathbf{R} ^ { d }$ whose union is unbounded, each having diameter bounded by a constant. If every $d + 1$ or fewer sets of $\mathcal{A}$ have a line transversal, then all the sets do.

Grünbaum's theorem.

([a6], [a10])

a) Let $\mathcal{A}$ be a collection of compact convex sets in $\mathbf{R} ^ { d }$, each lying in one of a collection of parallel hyperplanes. If every $2 d - 1$ or fewer sets of $\mathcal{A}$ have a line transversal, then $\mathcal{A}$ has a line transversal.

b) Let $\mathcal{A}$ be a collection of pairwise disjoint translates of a parallelogram. If every $5$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.

Danzer's theorem.

([a4]) Let $\mathcal{A}$ be a collection of pairwise disjoint unit discs in the plane. If every $5$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.

Grünbaum conjecture.

In view of these last two theorems, it was natural for B. Grünbaum to conjecture, in 1958 [a6], that for a collection of disjoint translates of a convex set, if every $5$ or fewer sets of the collection admit a line transversal, then the entire collection has a line transversal.

This conjecture remained open for over 30 years and its eventual solution involved an idea that had first appeared in a theorem of H. Hadwiger. The key observation is that while, without additional assumptions, a Helly-type theorem does not hold for arbitrary convex sets in the plane, by imposing a consistency condition on the order in which triples of a collection of convex sets are met by a line, one can recover the Helly property:

Hadwiger's transversal theorem.

([a12]) Let $\mathcal{A}$ be a finite collection of pairwise disjoint convex sets in $\mathbf{R} ^ { 2 }$. If there exists a linear ordering of $\mathcal{A}$ such that every $3$ members of $\mathcal{A}$ are met by a directed line in the corresponding order, then $\mathcal{A}$ has a line transversal.

A line transversal to any collection of disjoint convex sets meets the sets in a given order or its reverse, depending on the direction of the transversal. This pair of orders (permutations) is called a geometric permutation. Building on the fact that disjoint translates admit only few geometric permutations, H. Tverberg was able to prove Grünbaum's conjecture.

Tverberg's theorem.

([a16]) Let $\mathcal{A}$ be a collection of disjoint translates of a convex set in $\mathbf{R} ^ { 2 }$. If every $5$ or fewer members of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.

Hyperplane transversals.

Hadwiger's transversal theorem restored the generality and simplicity of Helly's theorem to the situation of Vincensini's problem. While it has been shown that no theorem of Hadwiger type holds for line transversals in $\mathbf{R} ^ { d }$ for $d \geq 3$, it turns out nevertheless that Hadwiger's theorem does generalize to hyperplane transversals in $\mathbf{R} ^ { d }$. This requires a notion of order for finite point sets in higher dimensions.

By the $k$-order type of a numbered set of points $P = \{ p _ { 1 } , \dots , p _ { n } \} \subset \mathbf{R} ^ { k }$ is meant the family of orientations of its $( k + 1 )$-tuples, i.e., the collection

\begin{equation*} \left( \text{sign det} \left( \begin{array} { c c c c } { 1 } & { p _ { i_0 } ^ { 1 } } & { \dots } & { p _ { i_0 } ^ { k } } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { 1 } & { p _ { i_k } ^ { 1 } } & { \cdots } & { p _ { i_ k } ^ { k } } \end{array} \right) \right) _ { 1 \leq i _ { 0 } < \ldots < i _ { k } \leq n } . \end{equation*}

This order type is simple if the set $P$ lies in general position in $\mathbf{R} ^ { k }$, i.e., if every determinant is non-zero.

A generalization of disjointness is also needed. Just as every directed line transversal to a collection of convex sets meets the sets in a unique, well-defined order if and only if the sets are disjoint, every $k$-transversal will meet them in a unique, simple $k$-ordering if and only if no $k + 1$ sets of the collection admit a $( k - 1 )$-transversal; such a collection is said to be $( k - 1 )$-separated. Thus, a collection is pairwise disjoint if and only if it is $0$-separated.

With these definitions, J.E. Goodman and R. Pollack proved the following generalization of Hadwiger's transversal theorem in arbitrary dimension.

Goodman–Pollack theorem.

([a7]) A $( d - 2 )$-separated collection $\mathcal{A}$ of compact convex sets in $\mathbf{R} ^ { d }$ has a hyperplane transversal if and only if there is a one-to-one correspondence between $\mathcal{A}$ and a set $S$ of points in $\mathbf{R} ^ { d-1 } $ such that every $d + 1$ sets of $\mathcal{A}$ are met by an oriented hyperplane consistently with the $( d - 1 )$-ordering induced on the corresponding points of $S$.

For this to hold, moreover, it is sufficient to find an acyclic rank-$d$ oriented matroid structure on $\mathcal{A}$ whose $( d + 1 )$-tuples satisfy the consistency condition of the theorem. (For the notion of oriented matroid, which can be thought of as a "locally realizable" generalization of the order type of a set of points, see also [a3].)

This theorem was subsequently generalized in several directions, the most comprehensive statement (which subsumes intermediate results of M. Katchalski and of Pollack and R. Wenger) being:

Anderson–Wenger theorem.

([a2]) Let $\mathcal{A}$ be a finite collection of connected sets in $\mathbf{R} ^ { d }$. $\mathcal{A}$ has a hyperplane transversal if and only if for some $k$, $0 \leq k < d$, there exists a rank-$( k + 1 )$ acyclic oriented matroid structure on $\mathcal{A}$ such that every $k + 2$ members of $\mathcal{A}$ are met by an oriented $k$-flat consistently with that oriented matroid structure.

Other directions.

An effort to understand intermediate-dimensional transversals leads to considering the set of all $k$-transversals to a collection of convex sets. While there are as yet (2000) very few non-trivial results about transversals of dimensions between $1$ and $d - 1$, there is a good deal known about the structure of these complete sets of transversals to collections of convex sets. It turns out that these subsets of the "affine Grassmannian" themselves behave very much like convex point sets. Although they need not be connected, they nevertheless share many properties with convex sets, such as being defined by a convex hull operator satisfying the anti-exchange property that commutes with non-singular affine transformations, and satisfying the Krein–Mil'man theorem [a8] (cf. also Locally convex space).

Other streams in geometric transversal theory include:

Gallai-type theorems, in which a Helly-type hypothesis leads to the conclusion that several transversals cover the entire collection (see [a1], [a18]);

the more general theorems of $( p , q )$ type, in which a hypothesis of the form "for every choice of p sets from the collection, some q have a common transversal" leads to a Gallai-type conclusion (see [a1], [a18]);

generalizations from transversal flats to transversal curves and surfaces (see [a9]);

ongoing work of L. Montejano on a topological generalization of Hadwiger's transversal theorem and on the related notion of a "separoid" ;

the problem of bounding the number of geometric permutations of a collection of $n$ convex bodies in $\mathbf{R} ^ { d }$, and its generalization (via order types) to $k$-transversals (see [a19]);

algorithmic geometric transversal theory, a branch of computational geometry (see [a19]).

Surveys include [a5], [a1], [a9], [a13], [a18], [a19], where many other references can be found.

References

[a1]	J. Eckhoff, "Helly, Radon, and Carathéodory type theorems" P.M. Gruber (ed.) J.M. Wills (ed.) , Handbook of Convex Geometry , North-Holland (1993) pp. 389–448
[a2]	L. Anderson, R. Wenger, "Oriented matroids and hyperplane transversals" Adv. Math. , 119 (1996) pp. 117–125
[a3]	A. Björner, M. Las Vergnas, N. White, B. Sturmfels, G.M. Ziegler, "Oriented matroids" , Cambridge Univ. Press (1993)
[a4]	L. Danzer, "Über ein Problem aus der kombinatorischen Geometrie" Archiv Math. , 8 (1957) pp. 347–351
[a5]	L. Danzer, B. Grünbaum, V. Klee, "Helly's theorem and its relatives" V. Klee (ed.) , Convexity , Proc. Symp. Pure Math. , 7 , Amer. Math. Soc. (1963) pp. 101–180
[a6]	B. Grünbaum, "On common transversals." Archiv Math. , 9 (1958) pp. 465–469
[a7]	J.E. Goodman, R. Pollack, "Hadwiger's transversal theorem in higher dimensions" J. Amer. Math. Soc. , 1 (1988) pp. 301–309
[a8]	J.E. Goodman, R. Pollack, "Foundations of a theory of convexity on affine Grassmann manifolds" Mathematika , 42 (1995) pp. 305–328
[a9]	J.E. Goodman, R. Pollack, R. Wenger, "Geometric transversal theory" J. Pach (ed.) , New Trends in Discrete and Computational Geometry , 10: Algorithms and Combinatorics , Springer (1993) pp. 163–198
[a10]	B. Grünbaum, "Common transversals for families of sets." J. London Math. Soc. , 35 (1960) pp. 408–416
[a11]	H. Hadwiger, "Über einen Satz Hellyscher Art." Archiv Math. , 7 (1956) pp. 377–379
[a12]	H. Hadwiger, "Über Eibereiche mit gemeinsamer Treffgeraden" Portugal. Math. , 16 (1957) pp. 23–29
[a13]	H. Hadwiger, H. Debrunner, V. Klee, "Combinatorial geometry in the plane" , Holt, Rinehart & Winston (1964)
[a14]	E. Helly, "Über Mengen konvexen Körper mit gemeinschaftlichen Punkten" Jahresber. Deutsch. Math. Verein. , 32 (1923) pp. 175–176
[a15]	L. Santaló, "Un teorema sobre conjuntos de paralelepipedos de aristas paralelas" Publ. Inst. Mat. Univ. Nac. Litoral , 2 (1940) pp. 49–60
[a16]	H. Tverberg, "Proof of Grünbaum's conjecture on common transversals for translates" Discr. Comput. Geom. , 4 (1989) pp. 191–203
[a17]	P. Vincensini, "Figures convexes et variétés linéaires de l'espace euclidien à $n$ dimensions" Bull. Sci. Math. , 59 (1935) pp. 163–174
[a18]	R. Wenger, "Helly-type theorems and geometric transversals" J.E. Goodman (ed.) J.O'Rourke (ed.) , Handbook of Discrete and Computational Geometry , CRC (1997) pp. 63–82 (Chap. 4)
[a19]	R. Wenger, "Progress in geometric transversal theory" B. Chazelle (ed.) J.E. Goodman (ed.) R. Pollack (ed.) , Advances in Discrete and Computational Geometry , Contemp. Math. , 223 , Amer. Math. Soc. (1999) pp. 375–393