tag:blogger.com,1999:blog-4115025577315673827.post5731957568905689155..comments2019-10-08T12:02:40.465+05:30Comments on CSE Blog - quant, math, computer science puzzles: Random point in a circleUnknownnoreply@blogger.comBlogger26125tag:blogger.com,1999:blog-4115025577315673827.post-11240126173816261342014-12-09T19:04:00.633+05:302014-12-09T19:04:00.633+05:30It does, thank you Pratik. Incidentally, I arrived...It does, thank you Pratik. Incidentally, I arrived at the solution myself shortly after I posted, but thanks for being prompt with your reply!Smigshttps://www.blogger.com/profile/05439265429149744731noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-81515554543592886672014-12-09T10:23:12.581+05:302014-12-09T10:23:12.581+05:30@Smigs
TPT: Generate two numbers uniformly between...@Smigs<br />TPT: 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.<br /><br />The probability that both number are less than r = r*r<br />Hence the probability distribution of the number generated satisfies our condition. Hence, its a correct solution.<br /><br />Hope that clarifies your doubt. Thanks<br />Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-52749907436217893092014-12-08T20:19:55.021+05:302014-12-08T20:19:55.021+05:30Sorry, but Vinayak and/or Pratik, could please pro...Sorry, but Vinayak and/or Pratik, could please provide more detail and explain why this works?Smigshttps://www.blogger.com/profile/05439265429149744731noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-77207660076411496322014-06-22T20:33:18.451+05:302014-06-22T20:33:18.451+05:30Prefect. Nice.Prefect. Nice.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-49635299732430332232014-06-22T20:32:40.161+05:302014-06-22T20:32:40.161+05:30Your point is not uniformly generated. See the pro...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.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38558856889095620312014-02-04T06:59:35.531+05:302014-02-04T06:59:35.531+05:30I think another way of generating an r such that r...I 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.Vinayakhttps://www.blogger.com/profile/10879814454563618581noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-73015819155767907172012-06-17T13:25:03.965+05:302012-06-17T13:25:03.965+05:30The question was to find a random point in the cir...The question was to find a random point in the circle<br />So, I am still not able to figure out the Jaadu's solution as to why he took r = sort(b).<br />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.<br />or I am not able to understand the notion of random point here ?Kapil Dubeyhttps://www.blogger.com/profile/00388428302950969251noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-18749848875150788312010-07-18T12:44:24.317+05:302010-07-18T12:44:24.317+05:30@saurabh..
1) They are same. Although the conditi...@saurabh.. <br />1) 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<br /><br />2) point probability is always zero.. you can assume that the random number we are taking is in [0, 2pi) or from (0, 2pi]Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-56106747048794830102010-07-07T18:52:23.868+05:302010-07-07T18:52:23.868+05:30I have two questions regarding the problem and its...I have two questions regarding the problem and its solution. Correct me if I am wrong.<br />1) 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?<br /><br />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?saurabhhttps://www.blogger.com/profile/09175541136404673214noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-16904676261599123522010-06-12T13:40:21.107+05:302010-06-12T13:40:21.107+05:30@abhi.. of course that is a solution.. I want a de...@abhi.. of course that is a solution.. I want a deterministic solution. Yours is a randomized one.<br /><br />As 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.<br /><br />Best of Luck!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-82549769352629564292010-06-11T03:21:34.420+05:302010-06-11T03:21:34.420+05:30hey, I don't think this would be a good soluti...hey, I don't think this would be a good solution..<br />consider a uniform distribution between 0 to 1 but with a very bad precision(in practice uniform dist always have finite precision) say <br />0,.25,.5,.5,.75,1<br /><br />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.<br /><br />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.<br /><br />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.abhihttps://www.blogger.com/profile/10718585328710156757noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-28868702026253540492010-05-28T11:48:33.475+05:302010-05-28T11:48:33.475+05:30@UrbanBlog.. Thanx..@UrbanBlog.. Thanx..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-15622818655574233492010-05-20T15:12:02.432+05:302010-05-20T15:12:02.432+05:30Thank you for this solution. I have implemented it...Thank you for this solution. I have implemented it in XNA: <a href="http://dzindzinovic.blogspot.com/2010/05/xna-random-point-in-circle.html" rel="nofollow">XNA Random Point In Circle</a>Urbanhttps://www.blogger.com/profile/11275203352292847827noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-29625311232175275092009-12-11T13:03:15.345+05:302009-12-11T13:03:15.345+05:30jaadu's explanation to his solution (which he ...jaadu's explanation to his solution (which he posted in some other post by mistake):<br /><br />"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."Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-74962850417311378072009-12-10T13:27:53.127+05:302009-12-10T13:27:53.127+05:30@asad, ramdas.. sorry..
wrote the problem casual...@asad, ramdas.. sorry.. <br /><br />wrote the problem casually.. updated now..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86311623460309426902009-12-10T12:00:37.363+05:302009-12-10T12:00:37.363+05:30agreed @asad...
PP, u have a P-blog, and you don&#...agreed @asad...<br />PP, u have a P-blog, and you don't even define what kind of PDF it should be...Ya, I Am A Dastardhttps://www.blogger.com/profile/04386601441575337262noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-30647649598521700212009-12-09T15:43:51.653+05:302009-12-09T15:43:51.653+05:30Yup. that's why I asked for the relation. So t...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.Asad Alihttps://www.blogger.com/profile/07133281473683565210noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-40733152531029768032009-12-08T12:32:37.363+05:302009-12-08T12:32:37.363+05:30@asad..
I was just thinking over ur comment. Even...@asad..<br /><br />I 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.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-5196021756326100062009-12-07T14:36:39.324+05:302009-12-07T14:36:39.324+05:30@jaadu.. correct answer
Trying to make the explana...@jaadu.. correct answer<br />Trying to make the explanation clear:<br /><br />For any small piece of theta (d\theta), since the probability has to be same.. theta is chosen uniformly from 0 to 2pi.<br /><br />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. :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-39560726587418133482009-12-07T14:26:41.347+05:302009-12-07T14:26:41.347+05:30create two random number between 0 and 1,say a and...create 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))jaaduhttps://www.blogger.com/profile/17923995765018410791noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-22397471196154669912009-12-07T14:20:50.062+05:302009-12-07T14:20:50.062+05:30angrezi thodhi kamzor hai :P.....angrezi thodhi kamzor hai :P.....jaaduhttps://www.blogger.com/profile/17923995765018410791noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-79115634438276021782009-12-07T14:03:37.807+05:302009-12-07T14:03:37.807+05:30@drunksaint (saurabh)
ur answer is wrong.. Lets pr...@drunksaint (saurabh)<br />ur 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.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-54217978921822786972009-12-07T14:00:47.635+05:302009-12-07T14:00:47.635+05:30theta=2.pi.a & r=b, where a&b: black box o...theta=2.pi.a & r=b, where a&b: black box outputs.drunksainthttps://www.blogger.com/profile/05334942021615777054noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-7862565053664685062009-12-07T12:28:34.786+05:302009-12-07T12:28:34.786+05:30@jaadu... the problem was to find a point in the c...@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<br /><br />Give me the algorithm to find a random point in a circle.<br /><br />@asad.. Hope that clarifies..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-71664126873483841712009-12-05T23:09:07.202+05:302009-12-05T23:09:07.202+05:30The problem statement is not very clear. Does ther...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 :)Asad Alihttps://www.blogger.com/profile/07133281473683565210noreply@blogger.com