Differences

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

--- courses:cs211:winter2014:journals:emily:entryseven [2014/03/12 00:39] – [Chapter 5.3] hardye
+++ courses:cs211:winter2014:journals:emily:entryseven [2014/03/25 19:10] (current) – [Seventh Entry] hardye
@@ Line 1: / Line 1: @@
-====== Seventh Entry ======
+====== Entry Seven ======
 ====== Chapter 5.2 ======
@@ Line 91: / Line 91: @@
 **Finding the Closest Pair of Points**
+The Problem:
+We are given a plane with a set of n points. Our goal is to find the pair of points that is closest together with a runtime of O(n log n).
+**The Algorithm:**
+We are given the set of points P where each point p<sub>i</sub> has coordinates (x<sub>i</sub>, y<sub>i</sub>) and d(p<sub>i</sub>, p<sub>j</sub>) is the distance between two points i and j. Our first step is to divide the points into two halves and find the smallest distance in both halves. Then we "combine" the halves and find the pair of points with the smallest distance with one point in one half and the other point in the other half. Recursion!!! We sort the points by their x coordinates into one list and again by their y coordinates into another list. Q is the set of points in the left half of the plane and R is the points in the right half of the plane. For each half we sort the points into two different lists by their x and y coordinates again which takes O(n) time. We then find the closest pair of points in Q and the closest pair of points in R. Now merging the solutions is the hard part. If there is no pair of points (q, r) whose distance is less than the minimum distance of Q and R then we have found our solution. The minimum distance of Q and R is denoted as z. If there is a pair of points (q, r) with a smaller distance, than those points must be within z of L (the line that separates Q and R). This allows us to minimize the set of points we are looking at.
+**(5.10)** If s, s' in S have the property that d(s, s') < z, then s and s' are within 15 positions of each other in the sorted list Sy.
+Proof: any two points in the same box are within the distance z*(sqrt2/2) < z which is a contradiction that z is the min distance between any pair in Q or R so each box has only one point in S.
+**Analysis:**
+Proof by induction that the algorithm correctly outputs a closest pair of points in P. The runtime of the algorithm is O(n log n). Sorting the points by their x and y coordinates takes O(n log n) time and the recurrence is T(n) =< 2T(n/2)+cn is O(n log n), so the whole algorithm is bounded by n log n.
+This section got really confusing when we were considering the subset S with all of the boxes and the distances. I'm still kind of confused by why the points have to be within 15 positions of each other. Overall it was readability: 8/10