@@ -302,12 +302,12 @@ Now we introduce a different randomized algorithm which is less practical but ve
302302- Take $\delta := \operatorname{dist}(p_1, p_2)$
303303- Partition the plane in squares of side $\delta/2$
304304- For $i = 1,2,\dots,n$:
305- - Take the square corresponding to $p_i$
306- - Interate over the $25$ squares within two steps to our square in the grid of squares partitioning the plane
307- - If some $p_j$ in those squares has $\operatorname{dist}(p_j, p_i) < \delta$, then
308- - Recompute the partition and squares with $\delta := \operatorname{dist}(p_j, p_i)$
309- - Store points $p_1, \dots, p_i$ in the corresponding squares
310- - else, store $p_i$ in the corresponding square
305+ - Take the square corresponding to $p_i$
306+ - Interate over the $25$ squares within two steps to our square in the grid of squares partitioning the plane
307+ - If some $p_j$ in those squares has $\operatorname{dist}(p_j, p_i) < \delta$, then
308+
309+
310+ - else, store $p_i$ in the corresponding square
311311- output $\delta$
312312
313313While this algorithm may look slow, because of recomputing everything multiple times, we can show the total expected cost is linear.
@@ -316,7 +316,7 @@ While this algorithm may look slow, because of recomputing everything multiple t
316316
317317We can therefore see that the expected cost is
318318
319- $$ O(n + \sum_{i=1}^{n} i \Pr(X_i = 1)) \le O(n + \sum_{i=1}^{n} i \frac{2}{i}) = O(3n) = O(n) \quad \quad \blacksquare $$
319+ $$ O\left (n + \sum_{i=1}^{n} i \Pr(X_i = 1)\right ) \le O\left (n + \sum_{i=1}^{n} i \frac{2}{i}\right ) = O(3n) = O(n) \quad \quad \blacksquare $$
320320
321321
322322##Generalization: finding a triangle with minimal perimeter