The algorithm for the Closest Point Pair problem (that we discussed in class) is

Question

The algorithm for the Closest Point Pair problem (that we discussed in class) is careful to ensure that it does O(n) work outside of the recursive calls. In this problem, I want to investigate the consequences of not being this careful, on the running time of algorithm for his problem. Specifically, suppose that instead of sorting the points initially (outside the recursion), we sort the points as needed (by x-coordinate and by y-coordinate) inside the recursive calls.

(a) Write down the recurrence relation that characterizes the running time of this new algorithm. (b) Solve this recurrence to obtain the running time of this new algorithm.

Explanation / Answer

Divide the input S into S 1,S2 by the median hyperplane normal to some axis.
Recursively compute Q1,Q2 for S1, 2 .
Let Set s1 = min( Q1,Q2) .
Let S0 be the set of points that are within ± of H ,projected onto H
Use the Q -sparsity condition to recursively examine all pairs in S 0 —there are only O ( n ) pairs.
The recurrence for the final algorithm is:
T ( n,d ) = 2 T( n= 2,d ) + U ( n,d-1) + O ( n )
           = 2 T ( n= 2 ,d ) + O ( n (log n ) d-2 ) + O ( n )
            = O ( n (log n ) d- 1 )
          
          This would give final recurrence
        T ( n,d ) = 2 T ( n= 2,d ) + O (n) + O (n) , which solves to O (n log n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.