18 - The Big Picture

Summary

As we have seen, many long-known problems from discrete geometry can be brought into the picture of monotone properties and parameters of configurations. Along the way, we have found obstacles and algorithms for many of these parameters.We have also shown thatmany pairs of these parameters are either equivalent for the purposes of fixed-parameter tractability (when each is bounded by a function of the other) or related by bounds in only one direction. Figure 18.1 shows some of these parameters and their relations.

In the next two sections, we summarize the key results about these properties and parameters.

Properties

COLLINEAR is the property of having all points on a single line (Definition 8.2). It may be tested in linear time (Section 8.4). There is only one collinear configuration of each size n, the configuration line(n). It has one obstacle, polygon(3).

CONVEX is the property of forming the vertices of a convex polygon (Definition 11.1). It may be tested in polynomial time by computing the convex hull (Section 11.4). There is only one convex configuration of each size n, the configuration polygon(n). It has a finite set of obstacles.

GENERAL-POSITION is the property of being in general position, true of point sets with no three in a line (Definition 9.1). Thus, it has one obstacle, line(3). It may be tested in quadratic time (Section 9.2).

INTEGER-COORDINATES(S) is the property of being realizable with integer coordinates, true of subconfigurations of grids (Definition 13.1). It includes all configurations in general position and all weakly convex configurations. We do not know its obstacles or computational complexity (Open Problem 13.4).

INTEGER-DISTANCES(S) is the property of being realizable with all pairwise distances equal to integers (Definition 13.1). It includes all configurations in convex position (Section 13.2). We do not know its obstacles or computational complexity (Open Problem 13.4).

STRETCHED is a property that characterizes the configurations generated by the stretching transformation (Definition 14.5), used to represent permutations by point sets (Observation 14.7). It may be tested in polynomial time (Theorem 14.23). Finding subconfigurations of stretched configurations is fixedparameter tractable (Theorem 14.26).

WEAKLY-CONVEX is the property of being in weakly convex position (Definition 12.1). It has a finite set of obstacles andmay be computed in polynomial time (Section 12.2). The weakly convex configurations are not well-quasiordered (Theorem 12.3).