12 - More on Convexity

Summary

A puzzle from the Russian mathematical olympiads asks for a proof that, for any convex pentagon of points in a grid, there is another grid point on or inside the smaller convex pentagon formed by the diagonals of the given pentagon (Figure 12.1). Thus, the grid has no empty pentagons. The existence or nonexistence of empty polygons is not a monotone property, but it suggests the study of other properties, beyond the basic ones studied in Chapter 11, based on what the convex polygons of a configuration contain and not just which points formtheir vertices.

Weak Convexity

A configuration S is in weakly convex position if none of the points is interior to the convex hull of S: each point either is a vertex of the convex hull (as in configurations that are in convex position) or lies on a convex hull edge. For instance, grid(2, n) is weakly convex for every n, but grid(3, 3) is not. It is tempting to guess that the weakly convex configurations are defined by the property FORBIDDEN(TETRAD), by analogy to the fact that convex = FORBIDDEN (TETRAD, LINE(3)). The three-point line is allowed in weakly convex positions, so it should be dropped fromthe list of obstacles.However, this guess is not quite right. There is one configuration that is not in weakly convex position but has no tetrad: the quincunx (Figure 12.2), a configuration formed from the four points of a convex quadrilateral together with one more point where the diagonals of the quadrilateral cross.

The two obstacles LINE(3) and TETRAD for convex position were derived from Carathéodory's theorem, that every point in the convex hull of a set of points belongs to the convex hull of two or three points from the set. The corresponding result for weakly convex position is Steinitz's theorem that every point interior to the convex hull is interior to the convex hull of three or four points from the set. Therefore, the two forbidden patterns for weakly convex position are the tetrad and the quincunx.