View source for Hoon Balakram

In [[Discrete geometry|discrete]] and [[computational geometry]], a set of points in the [[Euclidean plane]] 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.<ref name="m02"/> A [[finite set]] of points is in convex position if all of the points are [[Vertex (geometry)|vertices]] of their [[convex hull]].<ref name="m02"/> More generally, a [[family of sets|family]] of [[convex set]]s 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.<ref name="tv05"/>

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.<ref name="dhow06"/> Similarly, the [[minimum-weight triangulation]] is NP-hard for arbitrary point sets,<ref name="mr08"/> but solvable in [[polynomial time]] by [[dynamic programming]] for points in convex position.<ref name="k80"/>

The [[Erdős–Szekeres theorem]] guarantees that every set of ''n'' points in [[general position]] (no three in a line) has at least a logarithmic number of points in convex position.<ref name="es35"/> If ''n'' points are chosen uniformly at random in a [[unit square]], the probability that they are in convex position is<ref name="v95"/>
:<math>\left(\binom{2n-2}{n-1}/n!\right)^2.</math>

==References==
{{reflist|30em|refs=
<ref name="dhow06">{{citation
 | last1 = Deĭneko | first1 = Vladimir G.
 | last2 = Hoffmann | first2 = Michael
 | last3 = Okamoto | first3 = Yoshio
 | last4 = Woeginger | first4 = Gerhard J.
 | doi = 10.1016/j.orl.2005.01.002
 | issue = 1
 | journal = Operations Research Letters
 | mr = 2186082
 | pages = 106–110
 | title = The traveling salesman problem with few inner points
 | volume = 34
 | year = 2006}}.</ref>
<ref name="es35">{{citation
 | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős
 | last2 = Szekeres | first2 = George | author2-link = George Szekeres
 | journal = Compositio Mathematica
 | pages = 463–470
 | title = A combinatorial problem in geometry
 | url = http://www.numdam.org/item?id=CM_1935__2__463_0
 | volume = 2
 | year = 1935}}.</ref>
<ref name="k80">{{citation
 | last = Klincsek | first = G. T.
 | journal = Annals of Discrete Mathematics
 | pages = 121–123
 | title = Minimal triangulations of polygonal domains
 | volume = 9
 | year = 1980}}.</ref>
<ref name="m02">{{citation
 | last = Matoušek | first = Jiří | author-link = Jiří Matoušek (mathematician)
 | isbn = 978-0-387-95373-1
 | page = 30
 | publisher = Springer-Verlag
 | series = [[Graduate Texts in Mathematics]]
 | title = Lectures on Discrete Geometry
 | url = http://books.google.com/books?id=0N5RVe5lKQUC&pg=PA30
 | year = 2002}}.</ref>
<ref name="mr08">{{citation
 | last1 = Mulzer | first1 = Wolfgang
 | last2 = Rote | first2 = Günter
 | arxiv = cs.CG/0601002
 | doi = 10.1145/1346330.1346336
 | issue = 2
 | journal = [[Journal of the ACM]]
 | at = Article A11
 | title = Minimum-weight triangulation is NP-hard
 | volume = 55
 | year = 2008}}.</ref>
<ref name="tv05">{{citation
 | last1 = Tóth | first1 = Géza
 | last2 = Valtr | first2 = Pavel
 | contribution = The Erdős-Szekeres theorem: upper bounds and related results
 | location = Cambridge
 | mr = 2178339
 | pages = 557–568
 | publisher = Cambridge Univ. Press
 | series = Math. Sci. Res. Inst. Publ.
 | title = Combinatorial and computational geometry
 | volume = 52
 | year = 2005}}.</ref>
<ref name="v95">{{citation
 | last = Valtr | first = P.
 | doi = 10.1007/BF02574070
 | issue = 3-4
 | journal = [[Discrete and Computational Geometry]]
 | mr = 1318803
 | pages = 637–643
 | title = Probability that ''n'' random points are in convex position
 | volume = 13
 | year = 1995}}.</ref>
}}

[[Category:Convex hulls]]