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
Copy file name to clipboardExpand all lines: src/geometry/enclosing-circle.md
+3-3Lines changed: 3 additions & 3 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -13,19 +13,19 @@ Consider the following problem:
13
13
14
14
For each $p_i$, find whether it lies on the circumference of the minimum enclosing circle of $\{p_1,\dots,p_n\}$.
15
15
16
-
Here, by the minimum enclosing circle (MEC) we mean a circle with minimum possible radius that contains all the $n$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 $O(n^3)$, but actually works in $O(n)$ expected time.
16
+
Here, by the minimum enclosing circle (MEC) we mean a circle with minimum possible radius that contains all the $n$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 $O(n^3)$, but actually works in $O(n)$ expected time.
17
17
18
18
To better understand the reasoning below, we should immediately note that the solution to the problem is unique:
19
19
20
20
??? question "Why is the MEC unique?"
21
21
22
-
Consider the following setup: Let $r$ be the radius of the MEC. We draw a circle of radius $r$ around each of thep $p_1,\dots,p_n$. Geometrically, the centers of circles that have radius $r$ and cover all the points $p_1,\dots,p_n$ form the intersection of all $n$ circles.
22
+
Consider the following setup: Let $r$ be the radius of the MEC. We draw a circle of radius $r$ around each of thepoints $p_1,\dots,p_n$. Geometrically, the centers of circles that have radius $r$ and cover all the points $p_1,\dots,p_n$ form the intersection of all $n$ circles.
23
23
24
24
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 $r$ by a tiny bit, and still have non-empty intersection, which contradicts the assumption that $r$ was the minimum possible radius of the enclosing circle.
25
25
26
26
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 $p_i$ or two points $p_i$ and $p_j$ (it is also unique because its radius uniquely defines it).
27
27
28
-
Alternatively, we can also assume that there are two MECs, and then notice that their intersection (which containsp $p_1,\dots,p_n$ already) must have a smaller diameter than initial circles, and thus can be covered with a smaller circle.
28
+
Alternatively, we can also assume that there are two MECs, and then notice that their intersection (which containsthe points $p_1,\dots,p_n$ already) must have a smaller diameter than initial circles, and thus can be covered with a smaller circle.