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. Write down the recurrence relation that characterizes the running time of this new algorithm. Solve this recurrence to obtain the running time of this new algorithm.

Explanation / Answer

Closest pair of points problem

Closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean planewas among the first geometric problems which were treated at the origins of the systematic study of the computational complexity of geometric algorithms.

Algorithm

Closest-Pair( P )
if | P | = 2
then Return { P [1] , P [2] }
else x m <- the median x -coordinate
Partition P into two pieces: L = {( x i , x j ) -> P | x i = x m }
                               R = { ( x i , x j ) -> P | x i > x m }
{ p L , q L }<- Closest-Pair ( L )
{ p R , q R }<- Closest-Pair ( R)
P = L U R
if Distance ( p L , q L ) < Distance ( p R , q R )
then c <- { p L , q L }
d <- Distance ( p L , q L )
else c <- { p R ,q R }
d <- Distance ( p R , q R )
Discard points: P = { ( x i , x j ) -> P | xm - d < xi < xm + d }
Sort P by y -coordinate
for i <- 1 to | P |
do for j <- i + 1 to i + 7 and j < | P |
do if Distance ( P [ i ] , P [ j ]) < d
then c <- { P [ i ] , P [ j ] }
d <- Distance ( P [ i ] , P [ j ])
Return c

Divide and conquer is an important algorithm-design techni que in which a problem is partitioned into subproblems, the solutions to which can be combined to provide a solution to the whole problem. A few rules of thumb can be use d to evaluate the running time of the resulting algorithm:

1)A function that tak es time O (1) and then calls itself on a subproblem of size n - 1 takes time O ( n ). Examples are the factorial function and the merge function. F More generally, a function that takes time O ( n k ) and then calls itself on a subproblem of size n - 1 takes time O ( nk +1 ).

2)If a function calls itself twice but the recursion goes on for log 2 n levels,then the total running time is O ( n log n ) times the work done at each call, plus O ( n ) times the work done at the basis. In the case of merge sort, the work at each call, including basis calls, is O (1), so the total running time is O (n log n) + O (n), or just 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.