Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iv [2012/03/12 22:31] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iv [2012/03/13 01:58] (current) – [The Algorithm] mugabej
@@ Line 9: / Line 9: @@
 \\
+Let P = {p<sub>1</sub>,p<sub>2</sub>,...,p<sub>n</sub>} where p<sub>i</sub> has coordinates(x<sub>i</sub>,y<sub>i</sub>).
+For two points, p<sub>i</sub>,p<sub>j</sub> in P,d(p<sub>i</sub>,p<sub>j</sub>) = the Standard Euclidean distance between them.\\
+Our Goal: Find a pair of points (p<sub>i</sub>,p<sub>j</sub>) that minimizes d(p<sub>i</sub>,p<sub>j</sub>).\\
+**Our plan:** apply the divide and conquer style used in Mergesort by finding the closest pair among the points in the left half of P and the closest pair among the points on the right half of P, we then get the overall solution in O(n) time. With this plan, we can get an O(nlogn) running time.\\
+==== The Algorithm ====
+\\
+>>>>>>>>>>>>>>>>>>>>>>>>> Closest-Pair(p1, …, pn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Compute separation line L such that half the points\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> are on one side and half on the other side.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> δ1 = Closest-Pair(left half)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> δ2 = Closest-Pair(right half)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> δ = min(δ1, δ2)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Delete all points further than δ from separation line L\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Sort remaining points by y-coordinate.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Scan points in y-order and compare distance between each point and next 7 neighbors.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If any of these distances is less than δ, update δ.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> return δ\\
+\\
+The running time of this algorithm is O(nlogn).\\
+I give this section 8/10