If there are $8$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the open interval $\left(0,1\right)$, what is the expected largest size of a subset in which the points form the vertices of a convex polygon? Thanks!
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For specific and not very small $n$ this would be quit a messy computation. There are esults about the asymptotics for large $n$ in a paper of Ambrus and Barany http://arxiv.org/abs/0906.5452 . They consider a slightly different problem, but their methods work and the result is $c n^{1/3}$ for some computable $c$. Note also that they compute the typical value, which is only a lower bound for the expectation. Various concentration inequalities which apply since the points are iid can be used to get the expectation as well. (Or you could try to get a large deviation estimate directly.) 

