Forbidden Configurations in Discrete Geometry

Are there \(5\) points in the plane so that no three lie on a line and no four form a convex quadrilateral? What about \(9\) points so that no five form a convex pentagon? More generally, is there any \(k\) so that there are \(2^{k-2}+1\) points so that no \(k\) of them form a convex \(k\)-gon? This is what is known as the Happy Ending Problem, and it is one of the many examples of easy-to-state but hard-to-answer problems in discrete geometry.

David Eppstein is a computer science professor at University of California Irvine who is interested in these kind of problems, and he has adapted lectures he gave at the 2017 Canadian Conference on Computational Geometry into a new book entitled Forbidden Configurations in Discrete Geometry. The book has very few formal prerequisites but very quickly introduces a lot of technical machinery in order to address questions such as the Orchard-Planting Problem, asking how many lines with three or more trees one can have if one plants \(n\) trees in an orchard, or the No Three In A Row Problem, which asks how many pawns you can place on an \(n\times n\) chessboard so that no three lie in a row.

These topics might be familiar to some readers, and the area of Discrete Geometry is the subject of a number of other books, including the excellent Configurations of Points and Lines by Branko Grünbaum. But where Grünbaum approaches the subject as a mathematician and includes connections with topology and algebraic geometry, Eppstein approaches the subject as a computer scientist. As such, he is more concerned with issues of computational complexity, and spends quite a bit of time discussing issues about which problems are P or NP. For example, he gives a proof of the result that it is an NP-complete problem to determine whether any given configuration is a subset of another configuration.

Eppstein’s approach to these problems typically involves framing them as different parameters for configurations of points in the plane that satisfy a monotonicity property, meaning that removing a point will never increase the value of the parameter. He then looks at which values of these parameters can exist as well as studying their other properties and the relationships between different parameters. As an example, Eppstein shows that any configuration S of \(n\) points in the plane can be partitioned into a sequence of nested subconfigurations that are in convex position. He then defines the parameter ONION(S) to be the number of subconfigurations in this sequence. He gives results that ONION(S) can be computed in \(O(n \log(n))\) time, and then shows that it is at most the same as the number of points you need to delete from S to get a convex set as well as relating it to other parameters such as CONVEX-PARTITON(S), ONLINE(S), and SAWTOOTH(S).

There is a lot to like about this book, as Eppstein does a good job of introducing the material to his readers. I will note that I think many mathematicians will find certain aspects of Eppstein’s writing style and notational conventions to be different from what we are used to, and while I found his choice of topics interesting I know that the book made me think of many more questions that he did not address. A reader who sticks with Eppstein will learn a lot about this exciting area that lies on the border of mathematics and computer science.

Darren Glass is the Alumni Professor of Mathematics at Gettysburg College. His research interests include algebraic geometry, number theory, graph theory, and more.