Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter5 [2014/03/11 03:43] – [5.3 - Counting Inversions] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter5 [2014/03/12 00:47] (current) – [5.4 - Finding the Closest Pair of Points] tobind
@@ Line 69: / Line 69: @@
 ====== 5.4 - Finding the Closest Pair of Points ======
+**The Problem**
+Given //n// points in the plane, find the pair that is closest together.
+**Designing the Algorithm**
+Let us denote the set of points by //P = {p1, ..., pn}//, where //pi// has coordinates //(xi, yi)//; and for two points //pi, pj ∈ P//, we use //d(pi, pj)// to denote the standard Euclidean distance between them. Our goal is to find a pair of points //pi,pj// that minimizes //d(pi,pj)//. We will assume that no two points in //P// have the same //x//-coordinate or the same //y//-coordinate.
+We'll apply the style of divide and conquer used in Mergesort: we find the closest pair of points in the "left half" and the closest pair of points in the "right half" of //P// and then we use this information to get the overall solution in linear time. -> will give us an //O(n// log// n)// running time. Then we need to look at the distances between a point in the left half and a point in the right half. We need to find the smallest in //O(n)// time after the recursive calls returns.
+__Setting up the recursion:__ It will be useful if every recursive call on a set //P' ⊆ P//, begins with two lists: a list //Px'// in which all the points in //P'// have been sorted by increasing //x//-coordinate, and a list //Py'// in which all the points in //P'// have been sorted by increasing //y//-coordinate. Before any recursion occurs, we set up lists //Px// and //Py//. Attached to every entry in each list is a record of the position of that point in both lists.
+The first level of recursion will work as follows, with all further levels working in an analogous way. We define //Q// to be the set of points in the first //n///2 positions of the list //Px// and //R// to be the set in the final //n///2 positions of the list //Px//. By a single pass through each of //Px// and //Py// in //O(n)// time, we can create the following four lists: //Qx//, consisting of the points in //Q// sorted by increasing //x//-coordinate; //Qy//, consisting of the points in //Q// sorted by increasing //y//-coordinate; and analogous lists //Rx// and //Ry//. For each entry of each list, as before, we record the position of the point in both lists it belongs to.
+We now recursively determine a closest pair of points in //Q// (with access to the lists //Qx// and //Qy//). Suppose that //q0*, q1*// are returned as a closest pair of points in //Q//. Similarly, we obtain //r0*, r1*// from //R//.
+__Combining the Solutions:__ Let δ be the minimum of //d(q0*, q1*)// and //d(r0*, r1*)//. Are there points //q ∈ Q// and //r ∈ R// for which //d(q,r) < δ//? If not, then we have already found the closest pair in one of our recursive calls. But if there are, then the closest such //q// and //r// form the closest pair in //P//.
+Let //x*// denote the //x//-coordinate of the rightmost point in //Q// and let //L// denote the vertical line described by the equation //x = x*//. This line //L// "separates" //Q// from //R//. If there exists //q ∈ Q// and //r ∈ R// for which //d(q,r) < δ//, then each of //q// and //r// lies within a distance δ of //L//.
+Then, we can further say - There exists //q ∈ Q// and //r ∈ R// for which //d(q,r) < δ// if and only if there exist //s, s'∈ S// for which //d(s, s') < δ//.
+**Summary of the Algorithm**
+  Closest-Pair(P)
+     Construct Px and Py        (O(n log n) time)
+     (p0*, p1*) = Clostest-Pair-Rec(Px, Py)
+  Closest-Pair-Rec(Px, Py)
+     If |P| ≤ 3 then
+        find closest pair by measuring all pairwise distances
+     Endif
+     Construct Qx, Qy, Rx, Ry           (O(n) time)
+     (q0*, q1*) = Closest-Pair-Rec(Qx, Qy)
+     (r0*, r1*) = Closest-Pair-Rec(Rx, Ry)
+     δ = min(d(q0*, q1*), d(r0*, r1*))
+     x* =  maximum x-coordinate of a point in set Q
+     L = {(x,y) : x = x*}
+     S = points in P within distance δ of L
+     Construct Sy                      (O(n) time)
+     For each point s ∈ Sy, compute distance from s to each of next 15 points in Sy
+         Let s, s' be pair achieving minimum of these distances               (O(n) time)
+     If d(s,s') < δ then
+         Return (s, s')
+     Else if d(q0*, q1*) < d(r0*, r1*) then
+         Return(q0*, q1*)
+     Else
+         Return (r0*, r1*)
+     Endif
+**Analyzing the Algorithm**
+The algorithm correctly outputs a closest pair of points in P.
+The running time of the algorithm is //O(n //log// n)//.
+/10.
+====== 5.5 - Integer Multiplication ======
+**The Problem**
+Consider the  multiplication of two integers. Even though this seems trivial, the way that we are taught to compute it in school takes //O(n^2)// running time. But we can improve on that!
+**Designing the Algorithm**
+Let's assume we're in base-2 (but it doesn't matter) and start by writing //x// as //x1 * 2^(n/2) + x0//. In other words, //x1// corresponds to the "high-order" //n///2 bits and //x0// corresponds to the "low-order" //n///2 bits. Similarly, we write //y = y1 * 2^(n/2) + y0//. Thus, we have //xy = (x1 * 2^(n/2) + x0)(y = y1 * 2^(n/2) + y0) = x1y1 * 2^n + x1y0 _ x0y1)*2^(n/2) + x0y0//.
+This reduces the problem of solving a single //n//-bit instance to the problem of solving four //n///2-bit instances. -> recursviely compute the results for these four instances and then combine them using the above equation. The combining requires a constant number of additions of //O(n)//-bit numbers so it takes time //O(n)//; thus, the running time is bounded by the recurrence //T(n) ≤ 4T(n/2) + cn// for a constant //c//. ...good enough? NOPE.
+Try using three. This leads to //T(n) ≤ O(n^log2(q))//. The trick is to consider the result //(x1+x0)(y1+y0) = x1y1 + x1y0 + x0y1 + x0y0//.
+   Recursive-Multiply(x,y):
+   Write x = x1 * 2^(n/2) + x0
+         y = y1 * 2^(n/2) + y0
+   Compute x1+x0 and y1+y0
+   p = Recursive-Multiply(x1+x0, y1+y0)
+   x1y1 = Recursive-Multiply(x1,y1)
+   x0y0 = Recursive-Multiply(x0,y0)
+   Return x1y1 * 2^n + (p - x1y1 - x0y0) * 2^(n/2) + x0y0
+**Analyzing the Algorithm**
+Given two //n//-bit numbers, the alg performs a constant number of additions on //O(n)//-bit numbers, in addition to the three recursive calls.
+The running time satisfies: //T(n) ≤ 3T(n/2) + cn//.
+The running time of Recursive-Multiply on two //n//-bit factors is //O(n^log2(3)) = O(n^1.59)//