Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iv [2012/03/13 01:56] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_iv [2012/03/13 01:58] (current) – [The Algorithm] mugabej
@@ Line 22: / Line 22: @@
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> δ2 = Closest-Pair(right half)\\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> δ = min(δ1, δ2)\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Delete all points further than δ from separation
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Delete all points further than δ from separation line L\\
-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