You are here

Combinatorial Geometry in the Plane

H. Hadwiger and H. Debrunner
Publisher: 
Dover Publications
Publication Date: 
1966
Number of Pages: 
128
Format: 
Paperback
Price: 
14.95
ISBN: 
9780486789965
Category: 
Monograph
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Russell Jay Hendel
, on
01/8/2016
]

This is an excellent book that i) encourages the student to develop mathematical intuition and ii) helps him or her to understand the nature of mathematical research. The authors accomplish this by a) exposing the students to material that has strong intuitive appeal, b) using material currently researched by professional mathematicians, c) using elementary exercises that lead at once to more advanced and partially unsolved problems.

The content area of the book is combinatorial geometry, particularly problems in convexity, coverings and graphs. This short book (100 pages!) is modestly but powerfully organized around 100 theorems in the areas of incidence, integral distances, separability, Helly’s Theorem, covering problems, convexity, realization of distances, the point paradoxes, graphs and n-dimensional generalizations of results. The book has two halves; in the first half, theorems are stated which the student must prove or solve, while in the second half, short concise solutions or proofs may be found. This book could be used in a senior seminar, in a follow-up course to an introductory analysis course, or as a supplementary text in a discrete mathematics course. The prerequisites are modest: basic material and definitions from elementary geometry, analysis and real numbers with some exposure to set-theoretic reasoning and plane point sets.

The following illustrative examples gives the flavor of the results in the book. In this list, the book sometimes substitutes special cases of theorems for the general theorem statement.

  • Sylvester’s Theorem: If a finite set of points is such that on a line determined by any two of them there is always a third point of the set, then all the points lie on a single line
  • Erdős: If an infinite set of points is such that all of its points are at integral distances from each other, then all of the points like on a single line.
  • Helly’s Theorem: If each three ovals (bounded, closed convex sets) of a finite or infinite family of ovals have a common point, then all the ovals of the family have a common point.
  • Jung’s Theorem: The circumradius \(R\) of a point set of unit diameter, satisfies \(R^2\leq 1/3\).
  • The Plank Theorem: If an oval can be covered by two strips of breadths \(a\) and \(b\), it can be covered by a single strip of breadth \(a+b\).
  • Ramsey’s Theorem: If the p-pointed subsets of an infinite set A are divided into k classes, then A contains an infinite set all of whose p-pointed subsets belong to one class.
  • The Marriage Theorem: In a village one knows whether each person is friendly or not. What condition is necessary and sufficient for each boy to be able to marry a friendly girl?

A particularly nice feature of the book is the provision of nice, punchy proofs.

In the last section of the book, the translator provides n-dimensional analogs of some of the two-dimensional results brought earlier in the book. As every instructor knows, proving n-dimensional analogs of two dimensional results is an excellent undergraduate research exercise since it is typically within their grasp and yet constitutes bona-fide research activity. We illustrate with three pairs of results, the first being the 2-dimensional result and the 2nd being the n-dimensional result.

  • Caratheodory’s Theorem: A point is in the convex hull of a set in the plane iff it is in the convex hull of three or fewer points of the set
  • If \(X\) X is a subset of \(\mathbb{R}^n\), each point of the convex hull of \(X\) is a convex combination of \(n+1\) or fewer points of \(X\).
  • Steinitz’s Theorem: A point is an interior point of a convex hull of a set in the plane iff it is interior to the convex hull of four or fewer points of the set
  • If a point is interior to the convex hull of a set \(X\) in \(\mathbb{R}^n\), it is interior to the convex hull of some set of \(2n\) or fewer points of \(X\).
  • Radon’s Theorem: Each set of points in the plane that includes at least four points can be decomposed into two nonempty disjoint subsets that are not separable.
  • Each set of \(n+1\) or more points in \(\mathbb{R}^n\) can be divided into two disjoint sets whose convex hulls have a common point.

Bottom line: this charming book contains 100 delightful results on combinatorial geometry that are simply stated, elegantly proved, yet challenging to undergraduates.


Russell Jay Hendel (RHendel@Towson.Edu) holds a Ph.D. in theoretical mathematics and an Associateship from the Society of Actuaries. He teaches at Towson University. His interests include discrete number theory, pedagogy theory, applications of technology to education, problem writing, actuarial science and the interaction between mathematics, art and poetry.

The table of contents is not available.