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!
8
-
$\begingroup$ By the way, "size" only means cardinality here. $\endgroup$– user0oCommented Jan 17, 2013 at 20:14
-
$\begingroup$ Related: en.wikipedia.org/wiki/Happy_ending_problem $\endgroup$– Sam HopkinsCommented Jan 17, 2013 at 20:22
-
1$\begingroup$ Also posted to math.stackexchange.com/questions/280648/… originally with $16$ points, then edited to $4$ points. $\endgroup$– Gerry MyersonCommented Jan 17, 2013 at 22:02
-
2$\begingroup$ Probability distribution not clear: Are the points independent? For a given point, are the horizontal and vertical coordinates independent? $\endgroup$– Gerald EdgarCommented Jan 19, 2013 at 13:35
-
1$\begingroup$ 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. $\endgroup$– user0oCommented Jan 21, 2013 at 7:06
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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.)
-
$\begingroup$ 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. $\endgroup$– user0oCommented Jan 25, 2013 at 3:46
-
$\begingroup$ 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). $\endgroup$ Commented Apr 28, 2013 at 23:15