“Convex position”的意思、由来-开放百科全书

In 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.^[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.^[3]

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

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.^[7] If n points are chosen uniformly at random in a unit square, the probability that they are in convex position is^[8]

References

1. ^¹{{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}}.
2. ^¹{{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}}.
3. ^¹²{{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 = https://books.google.com/books?id=0N5RVe5lKQUC&pg=PA30 | year = 2002}}.
4. ^¹{{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}}.
5. ^¹{{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}}.
6. ^¹{{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}}.