Click here to Skip to main content
13,837,307 members
Rate this:
Please Sign up or sign in to vote.
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.


1 solution

Rate this: bad
Please Sign up or sign in to vote.

Solution 1

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)
int whichbucket(double x, double y, int n)
  double distsquared = x * x + y * y;
  return floor(distsquared * n);

AmitDey 8-Jun-12 8:44am
Thanks a lot Peter. that solves it.

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

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise | Privacy | Cookies | Terms of Service
Web01 | 2.8.190114.1 | Last Updated 7 Jun 2012
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100