Bucket Sort of Points in a Unit Circle

Question

0.00/5 (No votes)

See more:

This question is from the book "Introduction To Algorithms". I am looking for some help in solving this. I Apologize in advance for the long question. Also note that this is not homework ( I am not in school )

Exercise 8.4-4
We are given n points in the unit circle, , such that for . Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design a expected-time algorithm to sort the n points by their distances from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)

I understand the solution goes something like this-
Divide the area of the circle into n concentric circles. Area of each region will be 1/n. The radius corresponding to this would be Sqrt(1/n),Sqrt(2/n)...Sqrt(n/n)
Now for each point, calculate the radius and store in the corresponding bucket. Now perform the bucket sort.

My Question is how do I efficiently identify the bucket to which a Point P(x,y) belongs. If I check against each of the boundary values. It will take me O(n*n) only to identify the buckets.
Is there a better way to identify the bucket.

Thanks,
Amit

Posted 7-Jun-12 5:27am

AmitDey

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Peter_in_2780 · Accepted Answer · 2012-06-07T15:37:00

The clue is in the boundary radii. They are, as you say, sqrt(i/n) for i = 1 to n. Ugly, but their squares are nicely behaved - evenly spaced multiple of 1/n.
So the code would go something like this (depending on what language you are using)

C

int whichbucket(double x, double y, int n)
{
  double distsquared = x * x + y * y;
  return floor(distsquared * n);
}

Cheers,
Peter