Consider the following problem: Given a set of n points in the plane, p 1 = (x 1
ID: 3694328 • Letter: C
Question
Consider the following problem: Given a set of n points in the plane, p1 = (x1, y1), p2 = (x2, y2), . . . , pn = (xn, yn), determine which pair pi , pj are closest. The distance between any two points, pa = (xa, ya), pb = (xb, yb) in the plane is
((xa xb)2 + (ya yb)2 )
Write pseudocode to determine the two closest points among a collection of n points. Analyze it by: identifying the input/input size, identifying the elementary operation and how often it gets it gets executed with respect to the input size and provide an asymptotic characterization.
Explanation / Answer
Answer:
ClosestPair(Px, Py): if |Px| == 2: return dist(Px[1],Px[2]) // base
d1 = ClosestPair(FirstHalf(Px,Py)) // divide
d2 = ClosestPair(SecondHalf(Px,Py))
d = min(d1,d2) Sy = points in Py within d of L // merge
For i = 1,...,|Sy|:
For j = 1,...,15:
d = min( dist(Sy[i], Sy[j]), d )
Return d
Total Running Time Total Running Time:
• Divide set of points in half each time: O(log n) depth recursion
• Merge takes O(n) time.
• Recurrence: T(n) 2T(n/2) + cn
• Same as MergeSort =O(n log n) time.