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

1. Matoušek, Jiří (2002), Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer-Verlag, p. 30, ISBN 978-0-387-95373-1
2. Tóth, Géza; Valtr, Pavel (2005), "The Erdős-Szekeres theorem: upper bounds and related results", Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge: Cambridge Univ. Press, pp. 557–568, MR 2178339
3. Deĭneko, Vladimir G.; Hoffmann, Michael; Okamoto, Yoshio; Woeginger, Gerhard J. (2006), "The traveling salesman problem with few inner points", Operations Research Letters, 34 (1): 106–110, doi:10.1016/j.orl.2005.01.002, MR 2186082
4. Mulzer, Wolfgang; Rote, Günter (2008), "Minimum-weight triangulation is NP-hard", Journal of the ACM, 55 (2), Article A11, arXiv:cs.CG/0601002, doi:10.1145/1346330.1346336
5. Klincsek, G. T. (1980), "Minimal triangulations of polygonal domains", Annals of Discrete Mathematics, 9: 121–123, doi:10.1016/s0167-5060(08)70044-x, ISBN 9780444861115
6. Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry", Compositio Mathematica, 2: 463–470
7. Valtr, P. (1995), "Probability that n random points are in convex position", Discrete & Computational Geometry, 13 (3–4): 637–643, doi:10.1007/BF02574070, MR 1318803
8. Forge, David; Las Vergnas, Michel; Schuchert, Peter (2001), "10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope", Combinatorial geometries (Luminy, 1999), European Journal of Combinatorics, 22 (5): 705–708, doi:10.1006/eujc.2000.0490, MR 1845494