Happy Ending Problem - Related Problems

Related Problems

The problem of finding sets of n points minimizing the number of convex quadrilaterals is equivalent to minimizing the crossing number in a straight-line drawing of a complete graph. The number of quadrilaterals must be proportional to the fourth power of n, but the precise constant is not known.

It is straightforward to show that, in higher dimensional Euclidean spaces, sufficiently large sets of points will have a subset of k points that forms the vertices of a convex polytope, for any k greater than the dimension: this follows immediately from existence of convex k-gons in sufficiently large planar point sets, by projecting the higher dimensional point set into an arbitrary two-dimensional subspace. However, the number of points necessary to find k points in convex position may be smaller in higher dimensions than it is in the plane, and it is possible to find subsets that are more highly constrained. In particular, in d dimensions, every d + 3 points in general position have a subset of d + 2 points that form the vertices of a cyclic polytope. More generally, for every d and k > d there exists a number m(d,k) such that every set of m(d,k) points in general position has a subset of k points that form the vertices of a neighborly polytope.