Random point in a circle
This was the killer one. Interesting problem asked to me in one of the interviews.
You are given a black-box which returns a random number between 0 and 1. Give an algorithm to generate a point in the circle of radius 1.
(I was able to solve this but I must admit, its a difficult problem)
Update (December 10 2009) : To make things concrete: The black-box here returns a random number "uniformly" between 0 and 1. The question is to find a point "uniformly" in a unit circle. This would mean that the probability that a random point in the circle lies in a smaller concentric circle of radius r (r<1) is r^2. Solution by Jaadu in comments!!
You are given a black-box which returns a random number between 0 and 1. Give an algorithm to generate a point in the circle of radius 1.
(I was able to solve this but I must admit, its a difficult problem)
Update (December 10 2009) : To make things concrete: The black-box here returns a random number "uniformly" between 0 and 1. The question is to find a point "uniformly" in a unit circle. This would mean that the probability that a random point in the circle lies in a smaller concentric circle of radius r (r<1) is r^2. Solution by Jaadu in comments!!
use black box to generate a number a.
ReplyDeletelet theta = 2pi*a.Random Point in circle can then be taken as(cos(theta),sin(theta)).Another intersting problem is finding a random point in a sphere of radius 1.This problem is not as easy as finding random point from a circle.
The problem statement is not very clear. Does there need to be a relation between the black box output and the point. What is the relation. Simply speaking I can get an x,y by running the black box twice and draw a line from that to the centre. Wherever it intersects the unit circle is my answer. I'm pretty sure I've understood it wrong 'coz it couldn't be this simple :)
ReplyDelete@jaadu... the problem was to find a point in the circle and not on the circle. You gave the algorithm to find random point on the circle. This was "trivial". :P
ReplyDeleteGive me the algorithm to find a random point in a circle.
@asad.. Hope that clarifies..
theta=2.pi.a & r=b, where a&b: black box outputs.
ReplyDelete@drunksaint (saurabh)
ReplyDeleteur answer is wrong.. Lets prove this as follows: What is the probability that ur point is in the smaller circle of radius r/2. By your algorithm it is (2pi/2pi)*(r/2r) = 1/2. But it should be 1/4 as the area of inner circle is 1/4 of the total circle.
angrezi thodhi kamzor hai :P.....
ReplyDeletecreate two random number between 0 and 1,say a and b.Then theta = 2pi*a and r = squareroot(b).the take the point as (r*cos(theta),r*sin(theta))
ReplyDelete@jaadu.. correct answer
ReplyDeleteTrying to make the explanation clear:
For any small piece of theta (d\theta), since the probability has to be same.. theta is chosen uniformly from 0 to 2pi.
But r cannot be chosen uniformly. As area of a small segment is proportional to rdr. So, we want r such that r^2 is uniformly distributed. Hence we take r^2 to be a uniform distribution from 0 to 1. :)
@asad..
ReplyDeleteI was just thinking over ur comment. Even for point on a circle, your algorithm is incorrect as the areas on circle at 45, 135, 225, 315 degrees would have more probability.
Yup. that's why I asked for the relation. So the question should be rephrased as "generate a point within unit circle such that every point has the same probability" i.e. uniform distribution.
ReplyDeleteagreed @asad...
ReplyDeletePP, u have a P-blog, and you don't even define what kind of PDF it should be...
@asad, ramdas.. sorry..
ReplyDeletewrote the problem casually.. updated now..
jaadu's explanation to his solution (which he posted in some other post by mistake):
ReplyDelete"The idea in the previous post is that the probability of a point to be between r and r+dr is 2pi*r*dr.Hence to choose a radius we need to generate a number from random number generator which follows probability distribution 2*r.To generate random number which follows above probability distribution which follows uniform distribution we simply take the square root of the number generated by uniform distribution."
Thank you for this solution. I have implemented it in XNA: XNA Random Point In Circle
ReplyDelete@UrbanBlog.. Thanx..
ReplyDeletehey, I don't think this would be a good solution..
ReplyDeleteconsider a uniform distribution between 0 to 1 but with a very bad precision(in practice uniform dist always have finite precision) say
0,.25,.5,.5,.75,1
now with the method posted above the points would not be distributed equally in a small square at the periphery and the same square at the centre.
at the centre the square would at least have 1 point while near the periphery you can easily find an area where there is no probability of points falling.
I think a better way would be to generate the random points for a square just bigger than the circle and then reject points that fall outside the circle.
@abhi.. of course that is a solution.. I want a deterministic solution. Yours is a randomized one.
ReplyDeleteAs far as my solution being wrong is considered, select infinitely many points. Then the two probabilities would be equal. If you want to check in discrete space, see that as you increase the number of points, the two probabilities tend to become equal.
Best of Luck!
I have two questions regarding the problem and its solution. Correct me if I am wrong.
ReplyDelete1) if the probability distribution is uniform over the circle, shouldn't it mean that if we take any two enclosed regions inside the circle, each of area A, the probability of our point lying in each region will be same? If yes, then how do we show that the r^2 probability constraint and this condition are equivalent?
2)if we choose theta as 2pi times the random number generated in [0,1], then two of the outcomes of the black box, 0 and 1, will correspond to the same point in the circle. Doesn't it increase the probability of the points at 0 radians angle?
@saurabh..
ReplyDelete1) They are same. Although the condition that I am using looks weaker than yours, I can prove that both are equivalent. The condition I am taking is that probability in a small area of dr width at distance r and anguar change dtheta is same and so constant. So, integral over any area is a multiple of the area with a constant. Hence proved
2) point probability is always zero.. you can assume that the random number we are taking is in [0, 2pi) or from (0, 2pi]
The question was to find a random point in the circle
ReplyDeleteSo, I am still not able to figure out the Jaadu's solution as to why he took r = sort(b).
Considering polar co-ordinates, any point can be taken as (r,THETA). So, if two random numbers a and b are generated, then (b, 2*pi*a) will give equal probability of any two points inside the circle to be chosen with the same probability.
or I am not able to understand the notion of random point here ?
Your point is not uniformly generated. See the probability your point will lie in the circle(0,0,r/2)? Its supposed to give 1/4 as output.
DeleteI think another way of generating an r such that r^2 is uniform is this: Generate two numbers uniformly between 0 and 1 and pick the bigger of the two. The probability that the bigger one is between r and r+dr is proportional to r, which is exactly what we want.
ReplyDeletePrefect. Nice.
DeleteSorry, but Vinayak and/or Pratik, could please provide more detail and explain why this works?
Delete@Smigs
DeleteTPT: Generate two numbers uniformly between 0 and 1 and pick the bigger of the two. The distribution to the number selected is such that the probability that the number is less than r is proportional to r^2.
The probability that both number are less than r = r*r
Hence the probability distribution of the number generated satisfies our condition. Hence, its a correct solution.
Hope that clarifies your doubt. Thanks
It does, thank you Pratik. Incidentally, I arrived at the solution myself shortly after I posted, but thanks for being prompt with your reply!
Delete