<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="August19, 202515:59:22 UTC">August19, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="August23, 202522:03:07 UTC">August23, 2025</span>&emsp;

<p>You're given<spanclass="arithmatex">$n \leq 10^5$</span> points<spanclass="arithmatex">$p_i=(x_i, y_i)$</span>.</p>

<p>For each<spanclass="arithmatex">$p_i$</span>, find whether it lies on the circumference of the minimum enclosing circle of<spanclass="arithmatex">$\{p_1,\dots,p_n\}$</span>.</p>

<p>Here, by the minimum enclosing circle (MEC) we mean a circle with minimum possible radius that contains all the<spanclass="arithmatex">$n$</span>p, inside the circle or on its boundary. This problem has a simple randomized solution that, on first glance, looks like it would run in<spanclass="arithmatex">$O(n^3)$</span>, but actually works in<spanclass="arithmatex">$O(n)$</span> expected time.</p>

<p>Here, by the minimum enclosing circle (MEC) we mean a circle with minimum possible radius that contains all the<spanclass="arithmatex">$n$</span>points, inside the circle or on its boundary. This problem has a simple randomized solution that, on first glance, looks like it would run in<spanclass="arithmatex">$O(n^3)$</span>, but actually works in<spanclass="arithmatex">$O(n)$</span> expected time.</p>

<p>To better understand the reasoning below, we should immediately note that the solution to the problem is unique:</p>

<detailsclass="question">

<summary>Why is the MEC unique?</summary>

<p>Consider the following setup: Let<spanclass="arithmatex">$r$</span> be the radius of the MEC. We draw a circle of radius<spanclass="arithmatex">$r$</span> around each of thep<spanclass="arithmatex">$p_1,\dots,p_n$</span>. Geometrically, the centers of circles that have radius<spanclass="arithmatex">$r$</span> and cover all the points<spanclass="arithmatex">$p_1,\dots,p_n$</span> form the intersection of all<spanclass="arithmatex">$n$</span> circles.</p>

<p>Consider the following setup: Let<spanclass="arithmatex">$r$</span> be the radius of the MEC. We draw a circle of radius<spanclass="arithmatex">$r$</span> around each of thepoints<spanclass="arithmatex">$p_1,\dots,p_n$</span>. Geometrically, the centers of circles that have radius<spanclass="arithmatex">$r$</span> and cover all the points<spanclass="arithmatex">$p_1,\dots,p_n$</span> form the intersection of all<spanclass="arithmatex">$n$</span> circles.</p>

<p>Now, if the intersection is just a single point, this already proves that it is unique. Otherwise, the intersection is a shape of non-zero area, so we can reduce<spanclass="arithmatex">$r$</span> by a tiny bit, and still have non-empty intersection, which contradicts the assumption that<spanclass="arithmatex">$r$</span> was the minimum possible radius of the enclosing circle.</p>

<p>With a similar logic, we can also show the uniqueness of the MEC if we additionally demand that it passes through a given specific point<spanclass="arithmatex">$p_i$</span> or two points<spanclass="arithmatex">$p_i$</span> and<spanclass="arithmatex">$p_j$</span> (it is also unique because its radius uniquely defines it).</p>

<p>Alternatively, we can also assume that there are two MECs, and then notice that their intersection (which containsp<spanclass="arithmatex">$p_1,\dots,p_n$</span> already) must have a smaller diameter than initial circles, and thus can be covered with a smaller circle.</p>

<p>Alternatively, we can also assume that there are two MECs, and then notice that their intersection (which containsthe points<spanclass="arithmatex">$p_1,\dots,p_n$</span> already) must have a smaller diameter than initial circles, and thus can be covered with a smaller circle.</p>

<h2id="welzls-algorithm">Welzl's algorithm<aclass="headerlink"href="#welzls-algorithm"title="Permanent link">&para;</a></h2>

<p>For brevity, let's denote<spanclass="arithmatex">$\operatorname{mec}(p_1,\dots,p_n)$</span> to be the MEC of<spanclass="arithmatex">$\{p_1,\dots,p_n\}$</span>, and let<spanclass="arithmatex">$P_i = \{p_1,\dots,p_i\}$</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/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (100.0%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (98.09%)</li><li><ahref="https://github.com/MKLOL"title="MKLOL"data-bi-name="contributorprofile"target="_blank">MKLOL</a> (1.91%)</li></ul>