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.
Read more about this topic: Happy Ending Problem
Famous quotes containing the words related and/or problems:
“Gambling is closely related to theft, and lewdness to murder.”
—Chinese proverb.
“Our [adult] children have an adult’s right to make their own choices and have the responsibility of living with the consequences. If we make their problems ours, they avoid that responsibility, and we are faced with problems we can’t and shouldn’t solve.”
—Jane Adams (20th century)