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.^[1] A finite set of points is in convex position if all of the points are vertices of their convex hull.^[1] 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.^[2]

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.^[3] Similarly, the minimum-weight triangulation of planar point sets is NP-hard for arbitrary point sets,^[4] but solvable in polynomial time by dynamic programming for points in convex position.^[5]

The Erdős–Szekeres theorem guarantees that every set of ${\displaystyle 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.^[6] If ${\displaystyle n}$ points are chosen uniformly at random in a unit square, the probability that they are in convex position is^[7]

$${\displaystyle \left({\binom {2n-2}{n-1}}/n!\right)^{2}.}$$

The McMullen problem asks for the maximum number ${\displaystyle \nu (d)}$ such that every set of ${\displaystyle \nu (d)}$ points in general position in a ${\displaystyle d}$-dimensional projective space has a projective transformation to a set in convex position. Known bounds are ${\displaystyle 2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil }$.^[8]

References

This page was last edited on 18 December 2023, at 10:14