discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a g ...

and computational geometry, a set of points in the Euclidean plane or a higher-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

is said to be in convex position or convex independent if none of the points can be represented as a

convex combination In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other w ...

of the others. A

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...

of points is in convex position if all of the points are vertices of their convex hull. More generally, a

family Family (from la, familia) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its ...

convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...

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. An assumption of convex position can make certain computational problems easier to solve. For instance, the

traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

, NP-hard for arbitrary sets of points in the plane, is trivial for points in convex position: the optimal tour is the convex hull. Similarly, the minimum-weight triangulation of planar point sets is NP-hard for arbitrary point sets, but solvable in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...

for points in convex position. The

Erdős–Szekeres theorem In mathematics, the Erdős–Szekeres theorem asserts that, given ''r'', ''s,'' any sequence of distinct real numbers with length at least (''r'' − 1)(''s'' − 1) + 1 contains a monotonically increasing su ...

guarantees that every set of

n

points in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that ar ...

(no three in a line) in two or more dimensions has at least a logarithmic number of points in convex position. If

n

points are chosen uniformly at random in a

unit square In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and . Cartesian coordinates In a Cartesian coordin ...

, the probability that they are in convex position is

\left(\binom/n!\right)^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 In projective geometry, a homography is an isomorphism of projective spaces, induced by an isomorphism of the vector spaces from which the projective spaces derive. It is a bijection that maps lines to lines, and thus a collineation. In general, ...

to a set in convex position. Known bounds are

2d+1\le\nu(d)\le 2d+\lceil(d+1)/2\rceil

References

{{reflist, 30em, refs= {{citation , last1 = Deĭneko , first1 = Vladimir G. , last2 = Hoffmann , first2 = Michael , last3 = Okamoto , first3 = Yoshio , last4 = Woeginger , first4 = Gerhard J. , author4-link = Gerhard J. Woeginger , 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 {{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 {{citation , last1 = Forge , first1 = David , last2 = Las Vergnas , first2 = Michel , author2-link = Michel Las Vergnas , last3 = Schuchert , first3 = Peter , department = Combinatorial geometries (Luminy, 1999) , doi = 10.1006/eujc.2000.0490 , issue = 5 , journal =

European Journal of Combinatorics European, or Europeans, or Europeneans, may refer to: In general * ''European'', an adjective referring to something of, from, or related to Europe ** Ethnic groups in Europe ** Demographics of Europe ** European cuisine, the cuisines of Europe ...

, mr = 1845494 , pages = 705–708 , title = 10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope , volume = 22 , year = 2001, doi-access = free {{citation , last = Klincsek , first = G. T. , journal = Annals of Discrete Mathematics , pages = 121–123 , title = Minimal triangulations of polygonal domains , volume = 9 , year = 1980 , doi=10.1016/s0167-5060(08)70044-x {{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 Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standard ...

, title = Lectures on Discrete Geometry , url = https://books.google.com/books?id=0N5RVe5lKQUC&pg=PA30 , year = 2002 {{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 The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is Venkatesan ...

, at = Article A11 , title = Minimum-weight triangulation is NP-hard , volume = 55 , year = 2008 {{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 {{citation , last = Valtr , first = P. , doi = 10.1007/BF02574070 , issue = 3-4 , journal =

Discrete and Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geome ...

, mr = 1318803 , pages = 637–643 , title = Probability that ''n'' random points are in convex position , volume = 13 , year = 1995, doi-access = free Convex hulls