Combinatorial geometry

A branch of mathematics that unifies a circle of problems in which extremal properties of a combinatorial character are investigated for systems of figures. These problems are related, in the first instance, to optimal positioning (in a certain sense) of convex sets. An example of one of the oldest problems of this kind is the problem of the 13 spheres: What is the maximum number of material spheres of equal size that can be attached to a sphere of the same size in Euclidean space? J. Kepler, 1611, indicated the number 12, but a rigorous solution of this problem was provided in the middle of the 20th century by B.L. van der Waerden and K. Schütte.

Apparently the terminology "combinatorial geometry" first appeared in 1955 (see [1]). The beginnings of combinatorial geometry as an area of mathematics are usually associated with this year, although there are earlier results (see, e.g., [2]) that are related to it. Characteristic of combinatorial geometry is the visual nature of its problems. In combinatorial geometry, combinatorial arguments and combinations of examples from various areas of mathematics (topology, functional analysis, geometry in the large, graph theory, etc.) are extensively used. One of the central groups of problems in combinatorial geometry are problems on subdividing a figure into pieces (cf. Decomposition), e.g. the Borsuk problem.

A large group of problems in combinatorial geometry is formed by covering problems, in which one studies the possibility of covering a given set (cf. Covering (of a set)) by figures of a specified form (see, e.g., the Hadwiger hypothesis on the covering of a convex body by a minimal number of smaller bodies homothetic to it with homothety coefficient $k$, $0<k<1$; the illumination problem on the minimal number of directions of beams of parallel rays (or of sources) that will illuminate the boundary of a convex body, etc.).

Combinatorial geometry is closely related to discrete geometry; see, e.g., the Erdös problem on finding the maximum number of points in a Euclidean space $\mathbf R^n$ any three of which form a triangle with angles not exceeding $\pi/2$; this problem is connected in a certain way with the Hadwiger hypothesis and the illumination problem.

Combinatorial geometry touches closely on the theory of convex sets. See, e.g. the Helly theorem, which describes intersections of certain families of convex sets in dependence on the intersections of their subfamilies.

References

[1]	H. Hadwiger, "Eulers Charakteristik und kombinatorische Geometrie" J. Reine Angew. Math. , 194 (1955) pp. 101–110
[2]	P.S. [P.S. Aleksandrov] Alexandroff, H. Hopf, "Topologie" , 1 , Deutsch. Verlag Wissenschaft. (1935)
[3]	H. Hadwiger, H. Debrunner, "Kombinatorische Geometrie in der Ebene" , Monographie de l'Enseignement Math. , Genève (1959)
[4]	B. Grünbaum, "Borsuk's problem and related questions" V.L. Klee (ed.) , Convexity , Proc. Symp. Pure Math. , 7 , Amer. Math. Soc. (1963) pp. 271–284
[5]	H. Hadwiger, H. Debrunner, "Combinatorial geometry in the plane" , Holt, Rinehart & Winston (1964) (Translated from German)
[6]	I.M. Yaglom, "Combinatorial geometry" , Moscow (1971) (In Russian)
[7]	V.G. Boltyanskii, P.S. Soltan, "The combinatorial geometry of various classes of convex sets" , Kishinev (1978) (In Russian)

Comments

The number looked for in the above-mentioned problem of the 13 spheres is usually called the kissing number.

During the last two decades much attention has been paid to Radon's theorem and its generalizations by H. Tverberg (1966). An extensive survey is given in [a1]. Radon's theorem states: Each set of $d+2$ points in $\mathbf R^d$ can be expressed as the union of two disjoint subsets whose convex hulls (cf. Convex hull) have a common point. Moreover, $d+2$ is the smallest number with this property.

References

[a1]	J. Eckhoff, "Radon's theorem revisited" J. Tölke (ed.) J.M. Wills (ed.) , Contributions to geometry , Birkhäuser (1979) pp. 164–185