8
$\begingroup$

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.

  • 0
    Do you know anything about the dimension of your points?2012-12-07
  • 0
    Does "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
  • 1
    Jacob, all the points are in the $2$-dimensional Euclidean plane.2012-12-07
  • 1
    Jacob, yes, "boundary contains" means that the points are on the boundary. Thank you for making it clear.2012-12-07
  • 0
    alancalvitti, thank you for making it clear.2012-12-07
  • 0
    I 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
  • 0
    http://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
  • 0
    Gerry, 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
  • 1
    Erdos & 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
  • 0
    Dear 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
  • 0
    To 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
  • 0
    The 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
  • 0
    Note OP has posted a closely-related question, http://math.stackexchange.com/questions/253041/is-there-always-such-a-convex-hull2012-12-07
  • 0
    Dear 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

1 Answers 1