# Point sets with no empty quadrilateral

I know it's ridiculously late, but when I get ideas late at night I tend not to be able to sleep until I write them down, and here's as good a place as any for that.

Anyway, you remember (or probably you don't, but I do) that classification of dilation-free planar graphs I did a while back, that's now been incorporated into a paper with Dujmović, Suderman, and Wood?

A graph drawn with straight line segments in the plane is dilation-free if, for every pair of vertices \( x \) and \( y \), the graph contains a path along the line segment from \( x \) to \( y \). A set of vertices has a dilation-free planar graph if and only if (1) all points are on a line, (2) all but one point are on a line, (3) all but two points are on a line, those two points are on opposite sides of the line, and the line segment between them is outside the convex hull of the remaining points, (4) all but two points are on a line, those two points are on opposite sides of the line, and there is another point where the line segment between them crosses the line, or (5) the points form one sporadic six-point configuration:

So anyway, there's a much easier way to describe the same family of point sets, closely related to the famous happy ending problem: these are exactly the point sets that have no strictly-convex empty quadrilateral. They're also the point sets with exactly one triangulation.

In one direction, if there is a strictly-convex empty quadrilateral, its diagonals would cross so it couldn't form a dilation-free planar graph and there would be at least one triangulation for each diagonal. In the other direction, line segment \( xy \) will be formed by a path of edges in every triangulation of the point set unless there is a line segment \( zw \) that crosses \( xy \) not at a point of the point set. But in this case either \( xyzw \) form an empty quad or we can shrink to a smaller quad with a non-point crossing (by some case analysis involving replacing \( x \) or \( y \) by a point on \( xy \) if possible, or if not then replacing \( w \) or \( z \) by any point within the quad) and eventually find a strictly-convex empty quadrilateral.

It's known by now that every sufficiently large point set in general position has a strictly-convex empty hexagon but of course these point sets aren't in general position...