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.
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.
Combinatorial Geometry in the Plane
128
Combinatorial Geometry in the Plane
128eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
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.
Product Details
| ISBN-13: | 9780486799933 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 09/27/2014 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 128 |
| File size: | 20 MB |
| Note: | This product may take a few minutes to download. |
About the Author
Hans Debrunner also taught at Bern University.
Victor Klee (1925–2007) was Professor of Mathematics at the University of Washington in Seattle.
Read an Excerpt
Combinatorial Geometry in the Plane
By Hugo Hadwiger, Hans Debrunner, Victor Klee
Dover Publications, Inc.
Copyright © 1964 Holt, Rinehart & Winston, Inc.All rights reserved.
ISBN: 978-0-486-79993-3
CHAPTER 1
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. A short proof due to T. Gallai (Grünwald) is given by N. G. de Bruijn–P. Erdös, where the result appears as a corollary of a purely combinatorial theorem. For further proofs, generalizations, and variants see P. Erdös, H. S. M. Coxeter, G. A. Dirac, and Th. Motzkin.
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 A0 be a set of four points not lying on any line or circle. Then let an increasing sequence of finite sets An(n = 0,1, ···) be constructed recursively by setting
An = φ(An-1) (n = 1,2, ···),
where φ(A) 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 An 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).
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; for the case n = 3, see also G. Polya-G. Szegö, 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.
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 trigonometric theorem (Hadwiger).
8. If 0 < α < π/2 and the number cos α is rational, then either α = π/3 or α/π is irrational.
9. 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 lie on a single line.
This theorem of P. Erdös may serve as prototype for a certain category of results that are especially appealing in that strong and unexpected consequences are drawn from the simplest assumptions.
Remarkably, Proposition 9 does not imply the existence of a number k0 such that the conclusion always holds when the number k of points with exclusively integral distances is greater than k0. In fact, for each k there are such sets that are not linear, and even ones that have no three collinear points. Such point sets have been constructed repeatedly by M. Altwegg, A. Müller, F. Steiger, and others.
Following an idea of A. Müller, it is possible to describe a countably infinite point set that is dense in the unit circle, that is, intersects every arc of the circle, and has the property that all of its points are at rational distances from each other. Let Pn be the point with polar coordinates ρ = 1, θ = 2nφ, where φ is such that cos φ = 4/5, so that φ/π is irrational by Proposition 8. The points of the sequence Pn(n = 0,1, ···) are pairwise distinct, and the countably infinite set that they determine lies on the unit circle. It is dense in the circle and even uniformly distributed there, though we shall not define this notion precisely here. For the distance between any two of these points we have
d(Pn, Pm) = 2 | sin (n - m)φ|,
whose rationality follows from a well-known trigonometric identity and from the fact that sin φ = 3/5, cosφ = 4/5. Now, under an appropriate dilation, a similarity transformation of the plane, any k points of this set give rise to a set of k points having exclusively integral distances. Still no three of the points are collinear.
3. Hull Formation. Separability
The following group of propositions is concerned with hull formation and separation for plane point sets. First, some definitions. A set is called convex if with any two of its points it contains the entire line segment joining them. The convex hull of a set is the smallest convex set containing it. Alternatively, the convex hull is the intersection of all convex sets that contain the given set. A point is interior to a set if the set contains some circular disk centered at the point.
10. A point is in the convex hull of a set if, and only if, it is already in the convex hull of three or fewer points of the set.
From this it follows that the convex hull is identical with the union of all triangles whose vertices belong to the given set, or with a similar union of segments when the set is contained in a line.
11. A point is an interior point of the convex hull of a set if, and only if, it is interior to the convex hull of four or fewer points of the set.
Propositions 10 and 11 are the two-dimensional special cases of useful theorems of E. Steinitz and W. Gustin. See also O. Hanner-H. Rdström and C. V. Robinson.
Two sets will be called separable if there is a line that does not intersect either set and that separates them from each other; the two sets then lie interior to the two half planes that are determined by the line. The following criterion for separability is due to P. Kirchberger (see also H. Rademacher-I. J. Schoenberg).
12. Two bounded closed sets are separable if, and only if, any two of their subsets whose union includes at most four points are separable.
13. Each set that includes at least four points can be decomposed into two nonempty disjoint subsets that are not separable.
In this connection, see F. W. Levi and R. Rado.
4. Helly's Theorem. Transversal Problems for Ovals
We turn now to a circle of questions centered around the famous theorem of Helly. The numerous variants, Helly type theorems, which as a rule refer to ovals, form a very typical part of the combinatorial geometry of convex sets.
By an oval we understand here a bounded, closed convex set.
14. If each three ovals of a finite or infinite family of ovals have a common point, then all the ovals of the family have a common point.
This is the plane case of the well-known theorem of Helly. See E. Helly, J. Radon, D. König, and others. As one sees immediately from the simplest examples, the number three cannot be replaced by two. This is possible, however, with a strong assumption on the shape of the ovals. Thus the following variant is known.
15. If each two rectangles of a family of "parallel" rectangles, that is, with sides parallel to the coordinate axes, have a common point, then all the rectangles of the family have a common point.
In contrast, an oval that is not a parallelogram can be placed in three positions so that every two of the translates have a common point, but not all three. For parallelograms this is not possible. Thus parallelograms are characterized by a slightly modified version of the property expressed in Proposition 15. See B. Sz.-Nagy and especially Proposition 87 below.
A corollary of Proposition 15 is Helly's theorem for the line.
16. If each two segments of a family of segments (in the line) have a common point, then all the segments of the family have a common point.
Theorems of Helly type for the circle are closely related to Proposition 16 and are useful for many applications ; instead of ovals, these involve circular arcs, which obviously should lie on the same circle.
17. If a family of circular arcs, all smaller than a semicircle, is such that each three of the arcs have a common point, then all the arcs of the family have a common point.
The condition on the size of the arcs cannot be weakened, since the proposition is already false for semicircles. In fact, if four semicircles arise from two different pairs of antipodal points of the circle, then each three have a common point but not all four. Also, the number three in Proposition 17 cannot be replaced by two; of three equal arcs that just cover the entire circle, each two have a common point but not all three. On the other hand, the following is known.
18. If a family of circular arcs, all smaller than one third of a circle, is such that each two of the arcs have a common point, then all the arcs of the family have a common point.
For the next result, we drop all assumptions on the size of the arcs.
19. If a family of circular arcs is such that each two of the arcs have a common point, then there is an antipodal pair of points such that each arc of the family includes at least one point of the pair.
In other words, there is a diameter of the circle that intersects all the arcs. Theorems of this sort were found by C. V. Robinson and A. Horn-F. A. Valentine, among others. Some beautiful applications, such as those we shall describe later, were discovered by P. Vincensini.
20. If an oval can always be translated so that it is contained in the intersection of any three members of a family of ovals, then it can also be translated so that it is contained in the intersection of all the ovals of the family.
21. If an oval can always be translated so that it intersects any three members of a family of ovals, then it can also be translated so that it intersects all the members of the family.
22. If an oval can always be translated so that it contains any three members of a family of ovals, then it can also be translated so that it contains all of the members.
These are the plane cases of more general (higher-dimensional) variants of Helly's theorem, formulated by P. Vincensini and V. L. Klee, Jr.. For the validity of these results it is essential that the ovals should only be translated and not rotated. If the translation group is replaced by the group of rigid motions, then all three assertions become false.
We illustrate this more fully by an example connected with Proposition 21. Consider the family of n circular disks (n > 2) whose centers have polar coordinates ρ = 1 and θ = 2kπ/n(k = 1, ···, n), and whose radii are all equal to cos2 (π/n) or cos2 (π/n) + cos2 (π/2n) - 1 according to whether n is even or odd. As can be verified, a segment (degenerate oval) of length 2 can always be placed so as to intersect any n - 1 disks of the family but not to intersect all n of them. For this the segment must be suitably translated and rotated. The case n = 8 is illustrated by Figure 3.
23. If a family of ovals is such that each two of its members have a common point, then through each point of the plane there is a line that intersects all the ovals of the family.
24. If a family of ovals is such that each two of its members have a common point, then for each line in the plane there is a parallel line that intersects all the ovals of the family.
Propositions 23 and 24 are the plane cases of more general theorems of A. Horn and V. L. Klee, Jr.; they answer the question as to what can replace the conclusion of Helly's theorem when the number three is replaced by two in its hypothesis.
One may ask whether points can be replaced by lines in Helly's theorem, in the sense that an assertion of the following form is correct: If each h members of a family of ovals are intersected by a line, then there is a line that intersects all the ovals of the family. Does there exist such a Helly "stabbing number" h?
The answer is negative! L. A. Santaló has already observed that for each natural number n > 2 it is possible to construct a family of n ovals so that each n - 1 members of the family admit a common transversal, but not all n. This is illustrated also by our example in connection with Proposition 21. Theorems of the sort mentioned can be established only under supplementary conditions on the shape and position of the ovals involved. For example, Santaló proved that all of the rectangles of a family of parallel rectangles are intersected by a line if this is the case for each six rectangles of the family. We add here the following assertion, which contains Santaló's theorem.
25. If each three rectangles of a family of parallel rectangles are intersected by an ascending line, then there is an ascending line that intersects all the rectangles of the family.
We assume here that the sides of the rectangles are parallel to the axes of an orthogonal coordinate system; a line is said to be ascending if its slope is nonnegative. See Figure 4.
The earlier example (Figure 3), showing the nonexistence of a Helly stabbing number in the most general case, has the conspicuous feature that the ovals (disks) partially cover each other. Thus it is natural to ask whether a Helly stabbing number can be specified under the assumption that the ovals are pairwise disjoint. The answer to this question, posed by V. L. Klee, Jr., is again negative.
(Continues...)
Excerpted from Combinatorial Geometry in the Plane by Hugo Hadwiger, Hans Debrunner, Victor Klee. Copyright © 1964 Holt, Rinehart & Winston, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
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.
Dover (2014) republication of the edition originally published by Holt, Rinehart & Winston, New York, 1964.
See every Dover book in print at
www.doverpublications.com