Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 14 down vote favorite
2

If there are $4$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the interval $\left(0,1\right)$, what is the expected largest size (or cardinality) of a subset in which the points form the vertices of a convex polygon? Thanks.

share|improve this question
1  
For any particular arrangement, the subset you refer to has the same area as the convex hull of the points. This alternate phrasing might make computation easier to set up. Nice question. +1 – coffeemath Jan 17 at 11:28
A suggestion: For a start use 4 points instead of 16. – Christian Blatter Jan 17 at 12:41
@coffeemath: You seem to be taking "largest size" to mean "largest area"? I thought it referred to the cardinality of the set. – joriki Jan 17 at 14:20
@kejma: Could you clarify that please? – joriki Jan 17 at 15:00
Dear joriki, "largest size" here means largest cardinality or largest number of points in a subset. Thanks. – kejma Jan 17 at 16:32
show 4 more comments

1 Answer

up vote 3 down vote

The convex hull of four points consists of either $3$ or $4$ points, and this is also the cardinality of the largest subset of points forming a convex polygon. If the probability of $4$ points to form a convex quadrilateral is $p$, the expected cardinality of the largest subset is $p\cdot4+(1-p)\cdot3=3+p$.

The probability that $4$ points independently uniformly distributed in a square form a convex quadrilateral is given in the MathWorld article on Sylvester's four-point problem (along with various generalizations) as $25/36$. Thus the expected cardinality of the largest subset is $133/36$.

share|improve this answer
joriki, thank you very much for your answer, but do you know the probability that a convex quadrilateral occurs in $5$ random points? Thanks! – kejma Jan 17 at 21:20
@kejma: Yes, that probability is $1$. Either the convex hull has at least $4$ points, or it's a triangle containing two further points; the line through those two points intersects exactly two of the sides of the triangle; hence the two points form a convex quadrilateral with the endpoints of the remaining side of the triangle. – joriki Jan 17 at 21:41
joriki, thank you very much. How about the probability that a convex $6$-gon occurs in 8 random points? Thanks! – kejma Jan 17 at 22:13
@kejma: I think this is where it starts getting intractable. I suggest you look at the references given in the MathWorld article; they calculate the probability for all of $n$ points to form a convex polygon; perhaps you can use that for your more complicated question. I wrote some code to help you along; it takes two command line arguments, the total number of points and the number that you want to form a convex polygon; so in your question above the arguments would be $8$ and $6$. The probability for that is estiamted to be approximately $0.6904$. – joriki Jan 17 at 22:53
@kejma: You might be interested in this question and answer I just posted. – joriki Jan 19 at 18:24

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.