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
-
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
1 Answers
1
It is not always possible for large enough $n$. If $n = 2k$, take two collections of $k-1$ points and arrange them as two well separated small circular arcs (less than half-circles) facing away from each other - like )$\hspace{0.25in}$ (. The remaining $2$ points go at the midpoint of segment connecting the circles' centers.