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.

I ran into the following problem while working in neural nets.

Given natural numbers $b$ and $r$, uniformly randomly choose $b+r$ points within a unit square. Call the $b$ points the blue points and the $r$ points red points. What is the probability $p(b,r)$ that the convex hull of the blue points, $H_b$ , overlaps with $H_r$?

Partial answer : I can't immediately think of anything but a multi-fold brute-force integral for this. Intuitively, it seems to me (I could be incorrect) that $p(b,r)$ has to satisfy $\lim_{b\rightarrow \infty} p(b,r) = 1$ and likewise $p(b,r) \rightarrow 0$ as $b$ or $r$ approach 0. Also, given $b$ random points, we can compute the expected size of its convex hull according to this paper , though it's not clear to me how to use this.

I don't know how to connect these disparate hints at solution and would like suggestions.

share|improve this question
add comment

1 Answer 1

Edit: The below is wrong, as Robert Israel points out.

If you can find the expected area of the convex hull of $b$ blue points (call it $E[A]$), then the rest is easy. The probability that one red point, chosen uniformly and independently of the blue points, will lie in the convex hull is then again $E[A]$ (to see this, condition on the location of the blue points). So the probability that the convex hulls overlap is just the probability that some red point lies inside the convex hull of the blue points, which by independence is $1-(1-E[A])^r$.

share|improve this answer
1  
No: the convex hulls can overlap without any points of one colour lying inside the convex hull of the other colour. Consider e.g. the case of two red points and two blue points: the area of the convex hull of the red points is 0, but the probability of overlap is nonzero. –  Robert Israel Apr 3 '11 at 22:12
    
Oops. Silly of me. Edited. –  Nate Eldredge Apr 3 '11 at 22:41
add comment

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.