桶单位圆中的点排序 [英] Bucket Sort of Points in a Unit Circle

问题描述

这个问题来自算法简介"一书.我正在寻找一些帮助解决此问题的方法.对于这个冗长的问题，我事先表示歉意.另请注意，这不是家庭作业(我不在学校)

锻炼8.4-4
在单位圆中给我们n个点，例如.假设这些点是均匀分布的；也就是说，在圆的任何区域中找到一个点的概率与该区域的面积成正比.设计一个预期时间算法，以按距离原点的距离对n个点进行排序. (提示:在BUCKET-SORT中设计铲斗尺寸，以反映点在单位圆中的均匀分布.)

我知道解决方案是这样的-
将圆的面积划分为n个同心圆.每个区域的面积为1/n.与此对应的半径为Sqrt(1/n)，Sqrt(2/n)... Sqrt(n/n)
现在，对于每个点，计算半径并将其存储在相应的存储桶中.现在执行存储桶排序.

我的问题是如何有效地识别出P(x，y)点所属的存储桶.如果我检查每个边界值.我只需要O(n * n)即可识别铲斗.
有没有更好的方法来识别存储桶.

谢谢，
Amit

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

推荐答案

线索在边界半径内.如您所说，它们是i = 1至n的sqrt(i/n).丑陋，但它们的正方形表现良好-平均间隔为1/n的倍数.
因此，代码将像这样(取决于您使用的语言)

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

这篇关于桶单位圆中的点排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！