Classical Topics in Discrete Geometry

by K. Bezdek

Discrete and Combinatorial Geometry are two (often interchangeable) designations of a branch of mathematics that deals with finite combinations of geometric objects. If there is any distinction, the appellation "discrete" is associated more with the subject of optimal combinatorics than with the combinatorial questions per se.

I still own a small 1965 paperback Theorems and Problems of Combinatorial Geometry by V. G. Boltyanski and I. Z. Gohberg that I was fascinated with in high school. Most of the problems admitted simple formulations, with a minimum of mathematical jargon, and were of engagingly visual character. The simplicity of the formulations was rather deceptive. Even though the book was intended for high school students, it ended up with a list of unsolved problems. The first one was the famous Borsuk's Conjecture: Can every convex body in Rn be cut into (n + 1) pieces of smaller diameter? For bodies with smooth boundary, H. Hadwiger solved Barsuk's conjecture in 1946. For general bodies, it remained an open question for n ≥ 4. Problem 9, which later became Boltyanski-Hadwiger Illumination Conjecture, asked to prove that any convex body in Rn, n ≥ 2, can be illuminated by at most 2n infinitely distant light sources, with the maximum exclusively attained by the affine n-cube. (The problem was open for n ≥ 3.) Problem 13 posed a similar question for a number of finite light sources. These are the sort of problems that form the core of Discrete Geometry.

The book under review is centered around several topics: sphere packings (Chapter 1), packings by translates of convex bodies (Chapter 2), coverings by homothetic bodies and illumination (Chapter 3), coverings by planks and cylinders (Chapter 4), the volume of finite arrangements of spheres (Chapter 5), and ball-polyhedra (Chapter 6). The book has an unusual organization: it consists of two parts split roughly in the ratio 40:60. No statement in the first six chapters comes with a proof, be it a theorem or a conjecture. All the proofs in the book have been collected in the second part (Chapters 7-12.) The organization of the book is suggestive of the target audience.

An interested and discerning student can quickly scan the progression of the latest results for specific topics without getting boggled down in the details of the proofs. Indeed, the book is intended for graduate students interested in discrete geometry. The book provides a road map to the state-of-the-art of several topics in discrete geometry. It can also serve as a textbook for a graduate level course or a seminar. Additionally, the book is extremely current, with many references to as late as 2009-2010 publications. As the author writes in the Preface, The second part of the book is a collection of selected proofs that have been discovered in the last ten years, and have not appeared in any book or monograph. The majority of the proofs presented in the second part of the book have been developed by the author, or were results of the author's joint work with a number of colleagues. This feature makes the book a valuable source of information for a research mathematician.

Like the book of Boltyanski and Gohberg, the present one points to more than 40 research problems to encourage further interest in the subject. What about the problems that I mentioned? J. Kahn and G. Kalai disproved Barsuk's conjecture (p. 66) in 1993. It is now known that, for n sufficiently large, there exists a subset of the set of vertices of the unit cube in Rn such that to partition it into sets of smaller diameter requires more than (1.2)2 parts. The Illumination conjecture is still open for all n ≥ 3 despite the large number of partial results presently known. For example (p. 25), in R3 one needs at most 6 sources to illuminate a body of constant width. It's conjectured that, in this circumstance, the actual bound on the number of light sources is 4. The quest never ends.

One weakness of the book is the absence of an index which is only partially made up by the detailed captions of individual sections.

Classical Topics in Discrete Geometry, Springer. Hardcover, 166 pp, $49.95. ISBN 1-4419-0599-5.

|Up| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny