sinclair@aero.ARPA (William S. Sinclair) (10/24/85)
I will send $20.00 to the first person to give the answer. The problem is:
We select n points from a 2-dimensional uniform distribution, say {0 to 1}
in both x and y. Now we form the convex hull of these, and it will contain
k of the points. What is the probability that k of the n points will be on
the convex hull?
Hint: if n=3, p(k,n)=1.0
Also, as n goes to infinity, the expected value for k goes up like sqrt(n).
Bill S.
Go ahead and flame! I brought marshmallows!!
213/647-1753
P. S. The answers will be checked by a Monte Carlo simulation. You must include
the dervation of your formula.tedrick@ernie.BERKELEY.EDU (Tom Tedrick) (10/27/85)
>We select n points from a 2-dimensional uniform distribution, say {0 to 1} >in both x and y. Now we form the convex hull of these, and it will contain >k of the points. What is the probability that k of the n points will be on >the convex hull? Ouch! Offhand that looks like a hard research problem (worth more than $20). Has it been solved previously by anyone? -Tom
raghavan@ernie.BERKELEY.EDU (Prabhakar Raghavan) (11/01/85)
In article <511@aero.ARPA> sinclair@aero.UUCP (William S. Sinclair) writes: >We select n points from a 2-dimensional uniform distribution, say {0 to 1} >in both x and y. Now we form the convex hull of these, and it will contain >k of the points. What is the probability that k of the n points will be on >the convex hull? > >Hint: if n=3, p(k,n)=1.0 >Also, as n goes to infinity, the expected value for k goes up like sqrt(n). The latter hint is incorrect. Bentley, Kung, Schkolnick and Thompson (JACM 1978) showed that the expected number of points on the hull is O(log n) for a large class of distributions on the unnit square including the uniform distribution. In d-dimensions, it's O(log**d-1 n). The expected value O(sqrt(n)) holds when the points are uniformly distributed in a circle (I vaguely recall that the result is due to Renyi and somebody else). Intuitively, the corners in the square allow a few points to `dominate' a large number of the other points, resulting in fewer points on the hull; in a circle, no such corners exist. More recently, Luc Devroye of McGill Univ Computer Science has shown that the variance of the number of points on the hull (uniform on a square case) is O(log**2 n). Thus, with very high probability, the number of points on the hull is O(log n). I don't have a published reference for this, although I've read an unpublished manuscript. (For those that are interested, Devroye also showed that for points uniformly distributed in a d-dimensional hypercube, the variance is O(log**(2d-2) n) ). The significance of the result of Bentley &al is that there are convex hull algorithms that can be proved to run in expected linear time. .... Prabhakar Raghavan
sarwate@uicsl.UUCP (11/01/85)
The answer to this and related questions can be found in the book "Computational Geometry" by F. P. Preparata and M. I. Shamos (Springer-Verlag, 1985), and the references cited there.
bdm@anucsd.anu.OZ (Brendan McKay) (01/06/86)
If your turing machines (sorry, brains) have not been permanently blown
by thinking too much about polar bears, you might like to try your hands
at a *real* problem. The first correct solution, with justification,
will merit a prize of $1. (That's all I can afford, but think of the
fame, glory, etc.!)
A standard 52-card pack is dealt at random to 4 players. 13 cards each.
What is the probability that each player has at least 2 cards in each suit?
Don't bother replying if your answer is not between 20% and 21%.
Brendan McKay.
Computer Science Dept., Australian National University, GPO Box 4, ACT 2601,
Australia.
ACSnet: bdm@anucsd.anu.oz ARPA: bdm%anucsd.anu.oz@seismo
CSNET: bdm@anucsd.anu.oz@csnet-relay.csnet JANET: anucsd.anu.oz!bdm@ukc
UUCP: {decvax,vax135,pesnta,eagle}!mulga!anucsd.anu.oz!bdm
{seismo,ubc-vision,ukc,mcvax,prlb2}!munnari!anucsd.anu.oz!bdm
[ UUCP routes through munnari prefered ]carl@aoa.UUCP (Carl Witthoft) (01/08/86)
In article <505@anucsd.anu.OZ> bdm@anucsd.anu.OZ (Brendan McKay) writes: > >A standard 52-card pack is dealt at random to 4 players. 13 cards each. >What is the probability that each player has at least 2 cards in each suit? > >Don't bother replying if your answer is not between 20% and 21%. > Booooooooooooooooring!