Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
By the way, "size" only means cardinality here. –  user0o Jan 17 '13 at 20:14
    
Related: en.wikipedia.org/wiki/Happy_ending_problem –  Sam Hopkins Jan 17 '13 at 20:22
1  
Also posted to math.stackexchange.com/questions/280648/… originally with $16$ points, then edited to $4$ points. –  Gerry Myerson Jan 17 '13 at 22:02
2  
Probability distribution not clear: Are the points independent? For a given point, are the horizontal and vertical coordinates independent? –  Gerald Edgar Jan 19 '13 at 13:35
1  
Dear Gerald, yes, the random points are independent, and for a given point, the horizontal and vertical coordinates are also independent. Thank you for your questions that make this clear. –  user0o Jan 21 '13 at 7:06

1 Answer 1

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.)

share|improve this answer
    
Dear Omer, thank you for your answer, but do you know if the exponent would change for other convex regions? since they only considered a triangle. –  user0o Jan 25 '13 at 3:46
    
The exponent would not change. For example, take random points in a circular disk. Fit a triangle in the disk. A constant fraction of the n points falls inside the triangle (w.h.p.), and thus you get at least $c′n^{1/3}$ points in convex position; similarly, an ellipse (affine image of a disk) fits into any triangle, showing the other direction of the inequality. Any two convex shapes are related like this (after affine transformation). –  Günter Rote Apr 28 '13 at 23:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.