I just presented the Paul Erdős Memorial Lecture at the 29th Canadian Conference on Computational Geometry, in Ottawa, with a talk entitled “Forbidden Configurations in Discrete Geometry”. It’s called the Erdős Memorial Lecture because Erdős gave the first invited talk at the first CCCG. They tell me that a video of the talk will be made available at some point, and I’ll put a link here when it is, but for now here’s an online copy of my talk slides.

The talk was about the phenomenon that many important problems in discrete geometry involve properties of point sets that are both monotone (taking away points only makes some numerical value go down) and depend only on the orientations of triples of points (clockwise, counterclockwise, or collinear) rather than on the exact locations or distances of the points. For instance, the happy ending problem (the one I started my talk with) involves the size of the largest convex-position subset of a given set of points, which is monotone in this way. When you have a monotone property, you also have forbidden configurations, or obstacles, the minimal subsets of point sets that prevent you from having the property (in the case of a yes-or-no property) or from having a small property value (in the case of a numerical property). And when you have forbidden configurations, you can use them in the design of algorithms that test properties by searching for these obstacles.

There’s a huge industry in graph theory on hereditary properties of graphs (properties that are similarly monotone under vertex deletion, such as the size of the largest clique or independent set or the chromatic number) and my feeling is that it should be possible to build a similar theory in discrete geometry. But maybe it’s already there, under our noses, just not put together in a unified way. So the talk was my attempt to organize this material and show how many topics such as the no-three-in-line problem, onion layers, Tukey depth, universal point sets, etc., all fit into this common framework.

When I decided on this as the topic of my talk, last December, I started to write a survey paper for the proceedings to go with it. But there’s no survey there now, only an abstract that’s even shorter than this post. The reason is that, as I started to write it, it got away from me and grew into what is now a 250-page book draft with a signed book contract. So, the good news is that you can eventually read about it all in a lot more detail. The bad news is that it will be a year or so until it is out.

(G+)