Combinatorial Geometry in the Plane

Hugo Hadwiger, Hans Debrunner, Victor Klee

• Publisher: Dover Publications
• Year: 2014
• ISBN:
  9780486799933
• Topic: Mathématiques
• Subtopic: Géométrie

Geared toward advanced undergraduates familiar with analysis and college geometry, this concise book discusses theorems on topics restricted to the plane such as convexity, coverings, and graphs. In addition to helping students cultivate rigorous thought, the text encourages the development of mathematical intuition and clarifies the nature of mathematical research.
The two-part treatment begins with specific topics including integral distances, covering problems, point set geometry and convexity, simple paradoxes involving point sets, and pure combinatorics, among other subjects. The second part consists of an extensive section of short proofs concerning the earlier material.　

Part I

1. Incidence of Points, Lines, and Circles

The propositions of this first small group deal with incidence relations among points, lines, and circles, and thus pertain to combinatorial elementary geometry.

1. If a finite set of points is such that on the line determined by any two of the points there is always a third point of the set, then all the points lie on a single line.

This theorem was conjectured in 1893 by J. J. Sylvester [102]. A short proof due to T. Gallai (Grünwald) is given by N. G. de Bruijn–P. Erdös [9], where the result appears as a corollary of a purely combinatorial theorem. For further proofs, generalizations, and variants see P. Erdös [16], H. S. M. Coxeter [10], G. A. Dirac [13], and Th. Motzkin [76].

2. If a finite set of lines is such that through the intersection point of any two of the lines there always passes a third line of the set, then all the lines pass through a single point.

Propositions 1 and 2 are no longer true if the sets of points or lines are infinite. This is demonstrated for both theorems simultaneously by the example of the regular countably infinite system of points and lines pictured in Figure 1.

3. If a finite set of points, not all collinear, is such that on the circle determined by any three of the points there is always a fourth point of the set, then all the points lie on a single circle.

A set is said to be bounded if it lies in some circular disk of finite radius, closed if it includes all its limit points, where a point p is a limit point of a set X if every disk centered at p includes a point of X different from p. In both hypothesis and conclusion, the following theorem is closely related to Proposition 3.

4. If a bounded closed set of points is such that the axis of symmetry for any two of its points is always an axis of symmetry for the entire set, then all the points lie on a single circle.

It is easy to see that Propositions 3 and 4 are invalid for sets that are both infinite and unbounded. Indeed, it suffices to consider the entire plane as the set of points in question. An example consisting of countably many points may be constructed as follows : Let A₀ be a set of four points not lying on any line or circle. Then let an increasing sequence of finite sets A_n(n = 0,1, · · · ) be constructed recursively by setting

where φ(Α) denotes the union of all reflections of A in the various lines that are axes of symmetry for pairs of points in A. As one easily verifies, the union S of all the sets A_n is a countably infinite set with the desired property of symmetry. On the circle determined by any three points of S, there is always a fourth point of S as long as the three points do not determine an equilateral triangle (and even when they do if the construction φ is slightly extended).

Fig. 1

2. Integral Distances. Commensurable Angles

We present next a group of propositions in which a role is played by the integral or rational nature of certain distances.

The set of all points, whose coordinates with respect to an orthogonal coordinate system are both integers, forms the plane unit lattice; its points are called lattice points.

5. If n lattice points form a regular n-gon (n > 2), then n = 4; thus the square is the only regular polygon that can be embedded in the unit lattice.

An ingenious proof of this was given by W. Scherrer [93]; for the case n = 3, see also G. Polya-G. Szegö [82], 2, page 156, problem 238.

As is seen in Figure 2, a square can be embedded in the lattice in ways other than the obvious ones.

For the angles of embedded rhombi the following is known.

Fig. 2

6. If four lattice points determine a nonsquare rhombus with angle α, the quotient α/π is irrational; thus the square is the only rhombus that has angles commensurate with right angles and that can be embedded in the unit lattice.

Closely connected with this is an assertion about angles in Pythagorean triangles, that is, in right triangles whose sides have integral lengths.

7. If α is an acute angle of a Pythagorean triangle, the number α/π is irrational.

Propositions 6 and 7 are geometric corollaries of the following tri...