Credit Shamos for nearest pair of points algorithm

jxu · adamant-pwn · commit e1af371013e1 · 2023-01-29T22:14:39.000+01:00
Resolves cp-algorithms#969
diff --git a/src/geometry/nearest_points.md b/src/geometry/nearest_points.md
@@ -18,7 +18,7 @@ $$ \rho (p_i,p_j) = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} .$$
 
 The trivial algorithm - iterating over all pairs and calculating the distance for each — works in $O(n^2)$. 
 
-The algorithm running in time $O(n \log n)$ is described below. This algorithm was proposed by Preparata in 1975. Preparata and Shamos also showed that this algorithm is optimal in the decision tree model.
+The algorithm running in time $O(n \log n)$ is described below. This algorithm was proposed by Shamos in 1975. (Source: Ch. 5 Notes of _Algorithm Design_ by Kleinberg & Tardos, see references) Preparata and Shamos also showed that this algorithm is optimal in the decision tree model.
 
 ## Algorithm
 We construct an algorithm according to the general scheme of **divide-and-conquer** algorithms: the algorithm is designed as a recursive function, to which we pass a set of points; this recursive function splits this set in half, calls itself recursively on each half, and then performs some operations to combine the answers. The operation of combining consist of  detecting the cases when one point of the optimal solution fell into one half, and the other point into the other (in this case, recursive calls from each of the halves cannot detect this pair separately). The main difficulty, as always in case of divide and conquer algorithms, lies in the effective implementation of the merging stage. If a set of $n$ points is passed to the recursive function, then the merge stage should work no more than $O(n)$, then the asymptotics of the whole algorithm $T(n)$ will be found from the equation:
