13,837,307 members
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

## 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);
}```

Cheers,
Peter
AmitDey 8-Jun-12 8:44am

Thanks a lot Peter. that solves it.

Top Experts
Last 24hrsThis month
 Richard MacCutchan 195 Richard Deeming 190 Maciej Los 190 CHill60 75 OriginalGriff 65
 OriginalGriff 4,590 Maciej Los 2,125 Richard MacCutchan 1,823 RickZeeland 1,660 Patrice T 1,220