3
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ By the way, "size" only means cardinality here. $\endgroup$
    – user0o
    Jan 17, 2013 at 20:14
  • $\begingroup$ Related: en.wikipedia.org/wiki/Happy_ending_problem $\endgroup$ 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$ 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$ 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$
    – user0o
    Jan 21, 2013 at 7:06

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\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$
    – user0o
    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$ Apr 28, 2013 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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