You are here

Research Problems in Discrete Geometry

Peter Brass, William Moser, and János Pach
Springer Verlag
Publication Date: 
Number of Pages: 
Problem Book
[Reviewed by
Darren Glass
, on

In 1963, Leo Moser compiled a list of fifty problems in a mimeographed pamphlet under the title "Poorly formulated unsolved problems in combinatorial geometry" and distributed them at a number theory conference in Colorado. After Moser's death in 1970, his brother William Moser continued his work by compiling collections of problems in this area and reporting on progress made on the previous problems. Along the way he was joined in this project by Janos Pach and Peter Brass, and the latest edition of their book, now called Research Problems in Discrete Geometry has recently been released by Springer. This book collects hundreds of questions and open conjectures in the field, and discusses partial results which are known and techniques that people have tried to solve these questions. Before I discuss the book any further it is worth asking a simple question: What is discrete geometry? In an introduction that Paul Erdos wrote to an earlier version of the book, he alludes to the judge who cannot define pornography but knows it when he sees it:

As a matter of fact, I cannot even give a reasonable definition of the subject… Perhaps discrete geometry started with the feud between Newton and Gregory about the largest number of solid unit ball spheres that can be placed to touch a "central" unit ball sphere. Newton believed this number to be twelve, while Gregory believed it was thirteen. This controversy was settled in Newton's favor only late in the [nineteenth] century.

Brass, Moser, and Pach write about many problems in that spirit, all of which involve some combination of geometry, combinatorics, and number theory. There are balls being packed and planes being covered. There are points being placed in a plane to maximize or minimize all sorts of things. There are questions about planar graphs and others about isoperimetric inequalities. Some of the questions that I found particularly interesting include:

  • For a fixed n, what is the largest number k with the property that one can place n points in the unit square so that the minimum distance between them is at least k?
  • What is the largest number of congruent tetrahedra that can be determined by n points in three-dimensional space?
  • How can one arrange n overlapping unit balls in d-dimensional space to minimize the volume of the convex hull of their union?
  • Let n be an even integer. What is the maximum number of distinct ways that you can split n points in general position into two subsets of size n/2 by a single line?
  • What is the minimum number of colors for coloring the points of a plane so that no two points of the same color are at distance one from each other?
  • Can one pack a unit square with all of the rectangles whose dimensions are 1/i by 1/(i+1)?
  • Is it true that any set of n points in the plane has three elements that determine an angle at most π/n?
  • Does every planar graph have a straight-line drawing in which the length of every edge is an integer?

With hundreds of questions packed into fewer than 500 pages, it is clear that they do not stick with any given topic very long. The book very efficiently and clearly describes the relevant definitions and then states the problems and partial results, only occasionally pausing to give any larger mathematical context. And as is the case with any collection of open problems, reading this book leaves one craving the answers to these problems, and depending on your personality this could leave you either tantalized or very unsatisfied. This reviewer fell into the former camp, and on several occasions I found myself scribbling on a notepad half-convinced that I would find an elementary solution to the question I was considering, despite the fact that I have very little experience in either geometry or combinatorics. (I never did) The book is very well annotated, with a comprehensive bibliography after every set of problems that I often consulted during my readings. Brass, Moser, and Pach have done a very nice job in putting this collection together, and Research Problems in Discrete Geometry would be an excellent addition to any library or math department lounge.

Darren Glass ([email protected]) is an Assistant Professor at Gettysburg College.

 Preface.- Preface to an earlier version by Paul Erdos.- Definitions and Notations.- Density Problems for Packings and Coverings.- Structural Packing and Covering Problems.- Packing and Covering with Homothetic Copies.- Tiling Problems.- Distance Problems.- Problems on Repeated Subconfigurations.- Incidence and Arrangement Problems.- Problems on Points in General Position.- Graph Drawing and Geometric Graphs.- Lattice Point Problems.- Geometric Inequalities.- Author Index.- Subject Index.