Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:alyssa:chapter_5.4 [2014/03/11 22:22] – created hardnetta
+++ courses:cs211:winter2014:journals:alyssa:chapter_5.4 [2014/03/11 23:58] (current) – hardnetta
@@ Line 1: / Line 1: @@
 ====== Chapter 5.4: Finding the Closest Pair of Points ======
+Given //n// points on a plane, our goal is to find the pair that is closest together. Comparing every possible pairing would take O(n^2) time. However, it is possible to do this in O(nlogn) time.
+===== The Algorithm =====
+We will denote the set of points by //P={p_1,..., p_n}//, where //p_i// has coordinates //(x_i,y_i)//; and for two points //p_i,p_j//, //d(p_i,p_j)// to denote the Euclidean distance between them. We will also assume that all points have distinct coordinates. Our goal is to find a pair of coordinates //p_i// and //p_j// such that //d(p_i,p_j)// is minimized. We will approach this problem in a way that is similar to Mergesort: we will find the closest pair among the points in the left half of //P// and the closest pair among the right half of //P//.
+Closest-Pair(P):
+  * construct P_x and P_y (sorted lists by x and y coordinate, respectively)
+  * (p_0*,p_1*) = Closest-Pair-Rec(P_x,P_y)
+Closest-Pair-Rec(P_x,P_y):
+  * If |P|< = 3 then find closest pair by measuring all pairwise distances
+  * Construct Q_x,Q_y,R_x,R_y
+  * (q_0*,q_1*) = Closest-Pair-Rec(Q_x,Q_y)
+  * (r_0*,r_1*) = Closest-Pair-Rec(R_x,R_y)
+  * δ=min(d(q_0*,q_1*), d(r_0*,r_1*))
+  * x*=maximum x-coordinate of a point in set Q
+  * L={(x,y): x=x*}
+  * S= points in P within distance δ of L
+  * Construct S_y
+  * for each point s in S_y, compute distance from s to each of the next 15 points in S_y
+  * //Let s,s' be pair achieving minimum of these distances//
+  * If d(s,s')<δ then return (s,s')
+  * else if: if d(q_0*,q_1*) < d(r_0*,r_1*) then return (q_0*,q_1*)
+  * else: return (r_0*,r_1*)
+this runs in O(nlogn)
+I would rate this section a 6. The algorithm made more sense in class. I was really confused by all of the additional variables in this algorithm.