8.4-4

We are given n points in the unit circle, $p_i = (xi, yi) $, such that $0 \lt x^2+y^2 \leq 1$ for i = 1,2....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 $di = \sqrt {x^2_i+y^2_i} $ from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)

For the points to be uniformly distributed we need to divide the Area of the circle in to n parts since we are given n points. The n points needs to be uniformly distributed in to the n parts. Since all the points are with in the limits $0 \lt x^2+y^2 \leq 1 $ the area of the square is $\pi 1^2 = \pi$ we can divide the circle in to n parts by using n concentric circles(circles with same center see mathworld for more details ).

We can use $di = \sqrt {x^2_i+y^2_i} $ to place a point in a bucket but calculating square root of a number will take $\theta( log n)$ time to compute and this needs to be done for n inputs which will give us $\theta(n log n)$. But we need $\theta(n)$ time complexity algorithm.Let $r_0,r_1,r_3....r_n$ be radii of the concentric circles. $r_0$ is circle with 0 radius it is the center of the concentric circles. A point will lie between radii to two adjacent concentric circles. find $r_1$ $$\pi (r_1)^2-(r_0 )^2 = \pi /n $$ $$\pi . r_1^2 = \pi /n $$ $$\ r_1 = \sqrt {1 /n} $$ find $r_2$ $$\pi (r_2)^2-(r_1 )^2 = \pi /n $$ $$\pi (r_2)^2 - (\sqrt {1 /n} )^2 = \pi /n $$ $$ (r_2)^2 = 1/n + 1 /n $$ $$r_2 = \sqrt{2/n} $$ through the induction we can find for the rest of radii $r_i = \sqrt{i/n}$ $$ r_i \leq \sqrt {x^2_i+y^2_i} \lt r_{i+1} $$ $$ r_i \leq \sqrt {x^2_i+y^2_i} $$ $$ r_i = \sqrt {x^2_i+y^2_i} $$ $$\sqrt{i/n} = \sqrt {x^2_i+y^2_i} $$ $$i/n = x^2_i+y^2_i$$ $$i = n(x^2_i+y^2_i)$$ we need to use $n(x^2_i+y^2_i)$ to find the bucket for a point and sort again using insertion sort.
let Point be data structure with x,y,d as variables
bucket-sort-points(Point [] points )
let B[0..n] be the new array
for i =0..n
make B an empty array
for i = 0..points.length
let $x = {points(x)^2+points(y)^2}$
insert point[i] into list $B[ \lfloor x n \rfloor]$
for i = 0..n
sort list B[i] using insertionsort
concatenate B[0] B[1]...B[n] together