Combinatorial Geometry in the Plane

Kombinatorische Geometrie in der Ebene

Authors	Hugo Hadwiger, Hans Debrunner
Translator	Victor Klee
Language	German
Subject	Discrete geometry
Publisher	University of Geneva
Publication date	1960

Combinatorial Geometry in the Plane is a book in discrete geometry. It was translated from a German-language book, Kombinatorische Geometrie in der Ebene, which its authors Hugo Hadwiger and Hans Debrunner published through the University of Geneva in 1960, expanding a 1955 survey paper that Hadwiger had published in L'Enseignement mathématique. Victor Klee translated it into English, and added a chapter of new material. It was published in 1964 by Holt, Rinehart and Winston, and republished in 1966 by Dover Publications. A Russian-language edition, Комбинаторная геометрия плоскости, translated by I. M. Jaglom and including a summary of the new material by Klee, was published by Nauka in 1965. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.

Topics

The first half of the book provides the statements of nearly 100 propositions in the discrete geometry of the Euclidean plane, and the second half sketches their proofs. Klee's added chapter, lying between the two halves, provides another 10 propositions, including some generalizations to higher dimensions, and the book concludes with a detailed bibliography of its topics.

Results in discrete geometry covered by this book include:

• Carathéodory's theorem that every point in the convex hull of a planar set belongs to a triangle determined by three points of the set, and Steinitz's theorem that every point interior to the convex hull is interior to the convex hull of four points of the set.
• The Erdős–Anning theorem, that if an infinite set of points in the plane has an integer distance between every two points, then the given points must all lie on a single line.
• Helly's theorem, that if a family of compact convex sets has a non-empty intersection for every triple of sets, then the whole family has a non-empty intersection.
• A Helly-like property of visibility related to the art gallery theorem: if every three points of a polygon are visible from some common point within the polygon, then there is a point from which the entire polygon is visible. In this case the polygon must be a star-shaped polygon.
• The impossibility of covering a closed parallelogram by three translated copies of its interior, and the fact that every other compact convex set can be covered in this way.
• Jung's theorem, that (for sets in the plane) the radius of the smallest enclosing circle is at most $1/{\sqrt {3}}$ times the diameter. This bound is tight for the equilateral triangle.
• Paradoxes of set decomposition into smaller sets, related to the Banach–Tarski paradox.
• Radon's theorem that every four points in the plane can be partitioned into two subsets with intersecting convex hulls.
• Sperner's lemma on colorings of triangulations.
• The Sylvester–Gallai theorem, in the form that if a finite set of points in the plane has the property that every line through two of the points contains a third point from the set, then the given points must all lie on a single line.
• Tarski's plank problem, in the form that whenever two infinite strips together cover a compact convex set, their total width is at least as large as the width of the narrowest strip that covers the set by itself.
• Whenever a line is covered by two closed subsets, then at least one of the two subsets has pairs of points at all possible distances.

It also includes some topics that belong to combinatorics but are not inherently geometric, including:

• Hall's marriage theorem characterizing the bipartite graphs that have a perfect matching.
• Ramsey's theorem that, if the $k$-tuples of points from an infinite set of points are assigned finitely many colors, then an infinite subset has $k$-tuples of only one color.

Audience and reception

The book is written at a level appropriate for undergraduate students in mathematics, and assumes a background knowledge in real analysis and undergraduate-level geometry. One goal of the book is to expose students at this level to research-level problems in mathematics whose statement is readily accessible.