a better way. How?) Exercise 5.15. Given n points on the x-axis line (in some ar

Question

a better way. How?) Exercise 5.15. Given n points on the x-axis line (in some arbitrary order), find the closest pair of points in O(n log n) time . Show that the problem can be solved using sorting. Give a divide and conquer algorithm that does not use sorting. (The advantage of this approach is that it generalizes to points in higheir dimensions, e.g., 2 dimensions). (Hint: Partition the points into twa subproblems of equal size, recursively solve the subproblems, and ef- ficiently combine them to solve the original problem; exploit thefact that the recursion returns the closest pair in the respective subprob- lems.)

Explanation / Answer

Given n points on x-axis, closest pair of points can be found using sorting as follows: Find_closest(S): Input: set of points on x-axis Output: closest pair of points 1. Sort the points according to their x-cordinate. (Note:As the points are on x-axis, so y-cordinate of each point is 0.) 2. Find distance between each consecutive points and store in aaary L. i.e. L[i] stores distance between ith and (i+1)th point in sorted order. 3. Find minimum in L. The coresponding points are closest pair of points. Divide_conquer_closest_pair(S): Input: set of points on x-axis Output: closest pair of points 1. Find median point (say m) 2. Divide the points into two sets S1,S2 as follows: points having x-cordinate value less than or equal to m belong to S1 other points belong to S2. 3. d1=Divide_conquer_closest_pair(S1). 4. d2=Divide_conquer_closest_pair(S2). 5. d3=minimum distance across the cut. 6. return (d1,d2,d3). Running time of above algorithm: T(n)=2T(n/2)+O(n)=log n

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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