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

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

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

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)

Cheers,

Peter

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

Comments

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)

Copyright © CodeProject, 1999-2019

All Rights Reserved.

All Rights Reserved.

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