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:
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 (firstname.lastname@example.org) 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.