Suppose that $v_{1}$, $v_{2}$, $\ldots$,, $v_{2k}$ are $2k$ points in the plane. Is is true that there is always a convex hull of a subset of the $2k$ points such that at least $k$ of the $2k$ points are on the boundary of the convex hull? Thanks.
Does there always exist such a convex hull?
8
$\begingroup$
combinatorics
graph-theory
-
0Do you know anything about the dimension of your points? – 2012-12-07
-
0Does "boundary contains" mean that the points are on the boundary? – 2012-12-07
-
0@Jacob, Re dimension: OP wrote "in the plane" – 2012-12-07
-
1Jacob, all the points are in the $2$-dimensional Euclidean plane. – 2012-12-07
-
1Jacob, yes, "boundary contains" means that the points are on the boundary. Thank you for making it clear. – 2012-12-07
-
0alancalvitti, thank you for making it clear. – 2012-12-07
-
0I doubt it. The "Happy Ending" Theorem of Erdos and Szekeres concerns the number of points you need to guarantee a convex $k$-gon, and I think it's a lot more than $2k$, once $k$ gets big. $k=5$ may be big enough. – 2012-12-07
-
0http://en.wikipedia.org/wiki/Happy_Ending_problem suggests there's a set of 16 points, no 6 of which lie on the boundary of a convex polygon. – 2012-12-07
-
0Gerry, thank you for the link, but the question here is different from the Happy Ending problem, because the Happy Ending problem only allows the points at the boundary vertices of a convex hull but here the points can be on the boundary edges in addition to at the boundary vertices. – 2012-12-07
-
1Erdos & Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eotvos Sect. Math. 3-4 (1961) 53-63, available at http://www.renyi.hu/~p_erdos/1960-09.pdf construct a set of $2^{n-2}$ points which contains no convex $n$-gon. – 2012-12-07
-
0Dear Gerry, thank you for the reference. I believe that there is a set of $2^{n−2}$ points which contains no convex $n$-gon (in classic sense), but it is still possible that there is a convex $n-1$(or less)-gon(in classic sense) that has $2^{n−2}/2-(n-1)$ or more of the $2^{n−2}$ points on the boundary edges of the convex $n-1$(or less)-gon(in classic sense). – 2012-12-07
-
0To make it clear, if we define a general convex $n$-gon to be either the classic $n$-gon or a $m$-gon with $m-n$ points on some sides of the $m$-gon, then the main difference between this question and the Happy Ending problem is that this question asks about a general convex $n$-gon whereas Happy Ending problem is about a classic convex $n$-gon. – 2012-12-07
-
0The results I refer to always assume no three points on a line, so points on the sides of an $m$-gon do not arise. – 2012-12-07
-
0Note OP has posted a closely-related question, http://math.stackexchange.com/questions/253041/is-there-always-such-a-convex-hull – 2012-12-07
-
0Dear Gerry, exactly, their results assumed no three points on a line, but this question allows more points on the sides of an polygon and those points will be counted for this question. – 2012-12-07