<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="June26, 202519:43:19 UTC">June26, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="June28, 202518:31:49 UTC">June28, 2025</span>&emsp;

<h2id="linear-time-randomized-algorithms">Linear time randomized algorithms<aclass="headerlink"href="#linear-time-randomized-algorithms"title="Permanent link">&para;</a></h2>

<h3id="a-randomized-algorithm-with-linear-expected-time">A randomized algorithm with linear expected time<aclass="headerlink"href="#a-randomized-algorithm-with-linear-expected-time"title="Permanent link">&para;</a></h3>

<p>An alternative method arises from a very simple idea to heuristically improve the runtime: We can divide the plane into a grid of<spanclass="arithmatex">$d \times d$</span> squares, then it is only required to test distances between same-block or adjacent-block points (unless all squares are disconnected from each other, but we will avoid this by design), since any other pair has larger distancethat the two points in the same square.</p>

<p>An alternative method arises from a very simple idea to heuristically improve the runtime: We can divide the plane into a grid of<spanclass="arithmatex">$d \times d$</span> squares, then it is only required to test distances between same-block or adjacent-block points (unless all squares are disconnected from each other, but we will avoid this by design), since any other pair hasalarger distancethan the two points in the same square.</p>

<divstyle="text-align: center;">

<imgsrc="nearest_points_blocks_example.png"alt="Example of the squares strategy"width="350px">

<divclass="arithmatex">$$\frac{\lambda(x) n / 8}{n^2 / 2} = \frac{\lambda(x)/4}{n}$$</div>

<p>so the probability of at least one such pair being chosen during the<spanclass="arithmatex">$n$</span> rounds (and therefore finding a smaller<spanclass="arithmatex">$d$</span>) is</p>

<divclass="arithmatex">$$1 - \left(1 - \frac{\lambda(x)/4}{n}\right)^n \ge 1 - e^{-\lambda(x)/4}$$</div>

<p>(we have used that<spanclass="arithmatex">$(1 + x)^n \le e^{xn}$</span> for any real number<spanclass="arithmatex">$x$</span>, check<ahref="https://en.wikipedia.org/wiki/Bernoulli%27s_inequality#Related_inequalities">this Wikipedia page</a>).<br> Notice this goes to<spanclass="arithmatex">$1$</span> exponentially as<spanclass="arithmatex">$\lambda(x)$</span> increases. This hints that<spanclass="arithmatex">$\lambda$</span> will be small usually.</p>

<p>(we have used that<spanclass="arithmatex">$(1 + x)^n \le e^{xn}$</span> for any real number<spanclass="arithmatex">$x$</span>, check<ahref="https://en.wikipedia.org/wiki/Bernoulli%27s_inequality#Related_inequalities">Bernoulli inequalities</a>).<br> Notice this goes to<spanclass="arithmatex">$1$</span> exponentially as<spanclass="arithmatex">$\lambda(x)$</span> increases. This hints that<spanclass="arithmatex">$\lambda$</span> will be small usually.</p>

<p>We have shown that<spanclass="arithmatex">$\Pr(d \le x) \ge 1 - e^{-\lambda(x)/4}$</span>, or equivalently,<spanclass="arithmatex">$\Pr(d \ge x) \le e^{-\lambda(x)/4}$</span>. We need to know<spanclass="arithmatex">$\Pr(\lambda(d) \ge \text{something})$</span> to be able to estimate its expected value. We notice that<spanclass="arithmatex">$\lambda(d) \ge \lambda(x) \iff d \ge x$</span>. This is because making the squares smaller only reduces the number of points in each square (splits the points into other squares), and this keeps reducing the sum of squares. Therefore,</p>

<divclass="arithmatex">$$\Pr(\lambda(d) \ge \lambda(x)) = \Pr(d \ge x) \le e^{-\lambda(x)/4} \implies \Pr(\lambda(d) \ge t) \le e^{-t/4} \implies \mathbb{E}[\lambda(d)] \le \int_{0}^{+\infty} e^{-t/4} \, \mathrm{d}t = 4$$</div>

<p>(we have used that<spanclass="arithmatex">$E[X] = \int_0^{+\infty} \Pr(X \ge x) \, \mathrm{d}x$</span>, check<ahref="https://math.stackexchange.com/a/1690829">the proof</a>).</p>

<p>(we have used that<spanclass="arithmatex">$E[X] = \int_0^{+\infty} \Pr(X \ge x) \, \mathrm{d}x$</span>, check<ahref="https://math.stackexchange.com/a/1690829">Stackexchange proof</a>).</p>

<p>Finally,<spanclass="arithmatex">$\mathbb{E}[C(d)] = \mathbb{E}[\lambda(d) \, n] \le 4n$</span>, and the expected running time is<spanclass="arithmatex">$O(n)$</span>, with a reasonable constant factor.<spanclass="arithmatex">$\quad \blacksquare$</span></p>

<h4id="implementation-of-the-algorithm">Implementation of the algorithm<aclass="headerlink"href="#implementation-of-the-algorithm"title="Permanent link">&para;</a></h4>

<p>The advantage of this algorithm is that it is straightforward to implement, but still has good performance in practise.</p>

<p>While this algorithm may look slow, because of recomputing everything multiple times, we can show the total expected cost is linear.</p>

<p><strong>Proof.</strong> Let<spanclass="arithmatex">$X_i$</span> the random variable that is<spanclass="arithmatex">$1$</span> when point<spanclass="arithmatex">$p_i$</span> causes a change of<spanclass="arithmatex">$\delta$</span> and a recomputation of the data structures, and<spanclass="arithmatex">$0$</span> if not. It is easy to show that the cost is<spanclass="arithmatex">$O(n + \sum_{i=1}^{n} i X_i)$</span>, since on the<spanclass="arithmatex">$i$</span>-th step we are considering only the first<spanclass="arithmatex">$i$</span> points. However, turns out that<spanclass="arithmatex">$\Pr(X_i = 1) \le \frac{2}{i}$</span>. This is because on the<spanclass="arithmatex">$i$</span>-th step,<spanclass="arithmatex">$\delta$</span> is the distance of the closest pair in<spanclass="arithmatex">$\{p_1,\dots,p_i\}$</span>, and<spanclass="arithmatex">$\Pr(X_i = 1)$</span> is the probability of<spanclass="arithmatex">$p_i$</span> belonging to the closest pair, which only happens in<spanclass="arithmatex">$2(i-1)$</span> pairs out of the<spanclass="arithmatex">$i(i-1)$</span> possible pairs (assuming all distances are different), so the probability is at most<spanclass="arithmatex">$\frac{2(i-1)}{i(i-1)} = \frac{2}{i}$</span>, since we previously shuffled the points uniformly.</p>

<p>We can therefore see that the expected cost is

$$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 $$</p>

<spanclass="arithmatex">$<spanclass="arithmatex">$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$</span>$</span></p>

<h2id="generalization-finding-a-triangle-with-minimal-perimeter">Generalization: finding a triangle with minimal perimeter<aclass="headerlink"href="#generalization-finding-a-triangle-with-minimal-perimeter"title="Permanent link">&para;</a></h2>

<p>The algorithm described above is interestingly generalized to this problem: among a given set of points, choose three different points so that the sum of pairwise distances between them is the smallest.</p>

<p>In fact, to solve this problem, the algorithm remains the same: we divide the field into two halves of the vertical line, call the solution recursively on both halves, choose the minimum<spanclass="arithmatex">$minper$</span> from the found perimeters, build a strip with the thickness of<spanclass="arithmatex">$minper / 2$</span>, and iterate through all triangles that can improve the answer. (Note that the triangle with perimeter<spanclass="arithmatex">$\le minper$</span> has the longest side<spanclass="arithmatex">$\le minper / 2$</span>.)</p>

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

<spanclass="contributors-text">Contributors:</span>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/singamandeep"title="singamandeep"data-bi-name="contributorprofile"target="_blank">singamandeep</a> (48.8%)</li><li><ahref="https://github.com/izanbf1803"title="izanbf1803"data-bi-name="contributorprofile"target="_blank">izanbf1803</a> (46.71%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (2.1%)</li><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (1.5%)</li><li><ahref="https://github.com/Kostero"title="Kostero"data-bi-name="contributorprofile"target="_blank">Kostero</a> (0.3%)</li><li><ahref="https://github.com/SYury"title="SYury"data-bi-name="contributorprofile"target="_blank">SYury</a> (0.3%)</li><li><ahref="https://github.com/avishekp4"title="avishekp4"data-bi-name="contributorprofile"target="_blank">avishekp4</a> (0.3%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/singamandeep"title="singamandeep"data-bi-name="contributorprofile"target="_blank">singamandeep</a> (48.8%)</li><li><ahref="https://github.com/izanbf1803"title="izanbf1803"data-bi-name="contributorprofile"target="_blank">izanbf1803</a> (45.81%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (2.1%)</li><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (1.5%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (0.9%)</li><li><ahref="https://github.com/Kostero"title="Kostero"data-bi-name="contributorprofile"target="_blank">Kostero</a> (0.3%)</li><li><ahref="https://github.com/SYury"title="SYury"data-bi-name="contributorprofile"target="_blank">SYury</a> (0.3%)</li><li><ahref="https://github.com/avishekp4"title="avishekp4"data-bi-name="contributorprofile"target="_blank">avishekp4</a> (0.3%)</li></ul>