Convex position

In discrete and computational geometry, a set of points in the Euclidean plane or a higher-dimensional Euclidean space is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the others.Template:R A finite set of points is in convex position if all of the points are vertices of their convex hull.Template:R More generally, a family of convex sets is said to be in convex position if they are pairwise disjoint and none of them is contained in the convex hull of the others.Template:R

An assumption of convex position can make certain computational problems easier to solve. For instance, the traveling salesman problem, NP-hard for arbitrary sets of points in the plane, is trivial for points in convex position: the optimal tour is the convex hull.Template:R Similarly, the minimum-weight triangulation of planar point sets is NP-hard for arbitrary point sets, but solvable in polynomial time by dynamic programming for points in convex position.Template:R

The Erdős–Szekeres theorem guarantees that every set of $n$ points in general position (no three in a line) in two or more dimensions has at least a logarithmic number of points in convex position.Template:R If $n$ points are chosen uniformly at random in a unit square, the probability that they are in convex position isTemplate:R $${((\genfrac{}{}{0ex}{}{2n-2}{n-1})/n!)}^2.$$

The McMullen problem asks for the maximum number $\nu (d)$ such that every set of $\nu (d)$ points in general position in a $d$-dimensional projective space has a projective transformation to a set in convex position. Known bounds are $2d+1\le \nu (d)\le 2d+\lceil (d+1)/2\rceil$.Template:R