Take the 2-minute tour ×
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.

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 '13 at 11:28
    
A suggestion: For a start use 4 points instead of 16. –  Christian Blatter Jan 17 '13 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 '13 at 14:20
    
@kejma: Could you clarify that please? –  joriki Jan 17 '13 at 15:00
1  
Also posted (with $8$ points) to mathoverflow.net/questions/119208/… –  Gerry Myerson Jan 17 '13 at 22:03

1 Answer 1

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 '13 at 21:20
1  
@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 '13 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 '13 at 22:13
1  
@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 '13 at 22:53
    
@kejma: You might be interested in this question and answer I just posted. –  joriki Jan 19 '13 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.