We are given \(n\) points in the unit circle, \(p_i = (x_i, y_i)\), such that \(0 < x_i^2 + y_i^2 \leq 1\) for \(i = 1, 2, \ldots, n\). 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 an algorithm with an average-case running time of \(\Theta(n)\) to sort the \(n\) points by their distances \(d_i = \sqrt{x_i^2 + y_i^2}\) from the origin. (Hint: Design the bucket sizes in \(\textsc{Bucket-Sort}\) to reflect the uniform distribution of the points in the unit circle.)
The key insight is that uniform distribution in the circle means probability is proportional to area. Since area grows as \(r^2\), we need buckets of non-uniform width to get equal expected counts.
Think about concentric rings in the circle. For a ring from radius \(r_1\) to \(r_2\), the area is \(\pi r_2^2 - \pi r_1^2\). If points are uniformly distributed, the number of points in a ring is proportional to its area.
We want \(n\) buckets with equal expected number of points. Since the total area is \(\pi \cdot 1^2 = \pi\), each bucket should have area \(\pi/n\).
Bucket \(i\) (for \(i = 0, 1, \ldots, n-1\)) should contain points with distances in the range:
\[\sqrt{\frac{i}{n}} \leq d < \sqrt{\frac{i+1}{n}}\]This ensures each bucket corresponds to an annular region with area:
\[\pi \left(\frac{i+1}{n}\right) - \pi \left(\frac{i}{n}\right) = \frac{\pi}{n}\]
With uniform distribution, each bucket has expected size \(\Theta(1)\). Distributing points takes \(\Theta(n)\), sorting all buckets takes \(n \times O(1) = O(n)\), and concatenating takes \(\Theta(n)\). Total: \(\Theta(n)\) average-case time.