You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
<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>
6679
6689
</div>
6680
-
<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>
6690
+
<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>
6681
6691
<p>To better understand the reasoning below, we should immediately note that the solution to the problem is unique:</p>
6682
6692
<detailsclass="question">
6683
6693
<summary>Why is the MEC unique?</summary>
6684
-
<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>
6694
+
<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>
6685
6695
<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>
6686
6696
<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>
6687
-
<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>
6697
+
<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>
<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>