info prev up next book cdrom email home

Convex Polygon

A Polygon is Convex if it contains all the Line Segments connecting any pair of its points. Let $f(n)$ be the smallest number such that when $W$ is a set of more than $f(n)$ points in General Position (with no three points Collinear) in the plane, all of the Vertices of some convex $n$-gon are contained in $W$. The answers for $n=2$, 3, and 4 are 2, 4, and 8. It is conjectured that $f(n)=2^{n-2}$, but only proven that

2^{n-2}\leq f(n)\leq {2n-4\choose n-2},

where ${n\choose k}$ is a Binomial Coefficient.

© 1996-9 Eric W. Weisstein