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 is a collection of compact convex sets in , every or fewer members of which have a point in common, then there is a point common to all the members of .

A -transversal to a collection of sets is a -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 or fewer members of have a -transversal, then has a -transversal. In 1935, Vincensini [a17] asked whether there was a corresponding theorem for -transversals to a collection of convex sets in : Does there exist an such that for every collection of compact convex sets in , if every subcollection of at most members of has a -transversal, then has a -transversal?

Vincensini gave an incorrect proof that . Subsequently, several examples showed that no finite exists, even if it is assumed that the sets of 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 arbitrarily large, of unit discs in the plane (not disjoint) that do not have a line transversal even though any of them do. He also gave examples of disjoint unit balls in that have no plane transversal even though any of them do, for 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 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 be a collection of parallel rectangles in . If every or fewer elements of admit a line transversal, then admits a line transversal. The number cannot be reduced in general.

This generalizes in two directions to:

a) Let be a collection of parallelotopes in with edges parallel to the coordinate axes. If every or fewer elements of admit a line transversal, then admits a line transversal.

b) Let be a collection of parallelotopes in with edges parallel to the coordinate axes. If every or fewer elements of admit a hyperplane transversal, then admits a hyperplane transversal.

Hadwiger's theorem.

([a11], [a5]) Suppose is a collection of compact convex sets in whose union is unbounded, each having diameter bounded by a constant. If every or fewer sets of have a line transversal, then all the sets do.

Grünbaum's theorem.

([a6], [a10])

a) Let be a collection of compact convex sets in , each lying in one of a collection of parallel hyperplanes. If every or fewer sets of have a line transversal, then has a line transversal.

b) Let be a collection of pairwise disjoint translates of a parallelogram. If every or fewer elements of admit a line transversal, then has a line transversal.

Danzer's theorem.

([a4]) Let be a collection of pairwise disjoint unit discs in the plane. If every or fewer elements of admit a line transversal, then 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 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 be a finite collection of pairwise disjoint convex sets in . If there exists a linear ordering of such that every members of are met by a directed line in the corresponding order, then 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 be a collection of disjoint translates of a convex set in . If every or fewer members of admit a line transversal, then 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 for , it turns out nevertheless that Hadwiger's theorem does generalize to hyperplane transversals in . This requires a notion of order for finite point sets in higher dimensions.

By the -order type of a numbered set of points is meant the family of orientations of its -tuples, i.e., the collection

This order type is simple if the set lies in general position in , 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 -transversal will meet them in a unique, simple -ordering if and only if no sets of the collection admit a -transversal; such a collection is said to be -separated. Thus, a collection is pairwise disjoint if and only if it is -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 -separated collection of compact convex sets in has a hyperplane transversal if and only if there is a one-to-one correspondence between and a set of points in such that every sets of are met by an oriented hyperplane consistently with the -ordering induced on the corresponding points of .

For this to hold, moreover, it is sufficient to find an acyclic rank- oriented matroid structure on whose -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 be a finite collection of connected sets in . has a hyperplane transversal if and only if for some , , there exists a rank- acyclic oriented matroid structure on such that every members of are met by an oriented -flat consistently with that oriented matroid structure.

Other directions.

An effort to understand intermediate-dimensional transversals leads to considering the set of all -transversals to a collection of convex sets. While there are as yet (2000) very few non-trivial results about transversals of dimensions between and , 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 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 convex bodies in , and its generalization (via order types) to -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 à 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