====== 5.4 Finding the Closest Pair of Points ====== \\ ===== The Problem ===== \\ Given n points in the plane,find the pair that is closest together. The brute-force attempt at solving this problem would cost us O(n²) time. Our goal is to find an efficient algorithm that runs in O(nlogn) time.\\ \\ ==== Designing the Algorithm ==== \\ Let P = {p₁,p₂,...,p_n} where p_i has coordinates(x_i,y_i). For two points, p_i,p_j in P,d(p_i,p_j) = the Standard Euclidean distance between them.\\ Our Goal: Find a pair of points (p_i,p_j) that minimizes d(p_i,p_j).\\ **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