## Circumscribed Circle vs. Minimum Enclosing Circle II

Enough theory. It’s time to discuss how to compute the circle of minimum radius enclosing a finite set of points in the plane with the ultimate goal of finding a fast algorithm–deterministic or random–that we can implement on a computer. We first consider the case of three points. It turns out the smallest enclosing circle of three points is closely related to the circumscribed circle of a triangle.

Let $A, B, C$ denote the vertices of a triangle in $\mathbb{R}^{2}$. We adopt the convention that $a,b,c$ denote the lengths of the sides opposite the vertices $A,B,C$, respectively. We know that the circumscribed circle of the triangle $\triangle ABC$ exists and is unique, but where its center is located is uniquely determined by whether $\triangle ABC$ is acute, right, or obtuse. Furthermore, when the circumscribed circle coincides with the smallest enclosing circle is also uniquely determined by whether $\triangle ABC$ is acute, right, or obtuse.

Lemma 1. Given three points in $A,B,C$ in the plane, the point equidistant from all three is the intersection of the perpendicular bisectors of the sides of $\triangle$.

Proof. We know there exists a unique point equidistant from $A,B,C$, so it suffices to show given two points $x,y\in\mathbb{R}$, the locus of points equidistant from $x$ and $y$ is the span of the vector orthogonal to $x-y$.

Suppose $\left\|u-x\right\|^{2}=\left\|u-y\right\|^{2}$. I claim that $u-\frac{x+y}{2}\perp y-x$. Indeed,

$\begin{array}{lcl}\displaystyle\left\|u-y\right\|^{2}&=&\displaystyle\left\|u-x\right\|^{2}=\left\|u-y\right\|^{2}+2\langle{u-x,y-x}\rangle+\left\|y-x\right\|^{2}\\&\Longleftrightarrow&\displaystyle0=2\langle{u-y,y-x}\rangle+\left\|y-x\right\|^{2}\\&\Longleftrightarrow&\displaystyle0=\langle{u-y,y-x}\rangle+\langle{\frac{1}{2}(y-x),y-x}\rangle=\langle{u-\frac{1}{2}(y+x),y-x}\rangle,\end{array}$

which shows that $\left\{u\in\mathbb{R}^{d}: \left\|u-x\right\|^{2}=\left\|u-y\right\|^{2}\right\}=\left\{u\in\mathbb{R}^{d}:\langle{u-\frac{x+y}{2},y-x}\rangle=0\right\}$. $\Box$

This lemma tells the geometer how to locate the circumcenter with a compass and ruler.

Theorem 2.

1. The circumcenter is located in the interior of $\text{co}\left\{A,B,C\right\}$ if and only if $\triangle ABC$ is acute.
2. The circumcenter is located on the hypotenuse of $\triangle ABC$ if and only if $\triangle ABC$ is right.
3. The circumcenter is located outside $\text{co}\left\{A,B,C\right\}$ if and only if $\triangle ABC$ is obtuse.

Acute Circumscribed Circle

Right Circumscribed Triangle

Obtuse Circumscribed Circle

###### (Images from Wikipedia)

Proof. Since acute, right, and obtuse are mutually exclusive, it suffices to prove only necessity in each statement. Define points $D, E, F$ by

$\displaystyle D:=\frac{A+B}{2},\indent E:=\frac{B+C}{2},\indent F:=\frac{A+C}{2}$

Suppose the circumcenter $O$ is located in the interior. Since $\triangle AOC$, $\triangle AOB$, $\triangle BOC$ are isosceles (recall that $O$ is by definition equidistant from each vertex), we can write

$\angle AOC={\angle AOD}+{\angle BOD}=2\theta_{1},\angle AOB={\angle AOF}+{\angle COF}=2\theta_{2},\angle BOC=\angle BOE+\angle EOC=2\theta_{3}$

where $0^{\circ}<\theta_{1},\theta_{2},\theta_{3}<90^{\circ}$. Furthermore,

$2\theta_{1}+2\theta_{2}+2\theta_{3}=360^{\circ}\Longrightarrow\theta_{1}+\theta_{2}+\theta_{3}=180^{\circ}$

Hence, $\theta_{1}+\theta_{2},\theta_{1}+\theta_{3},\theta_{2}+\theta_{3}>90^{\circ}$, which is equivalent to $\triangle ABC$ being acute.

Suppose the circumcenter $O$ is located on the boundary $\triangle ABC$. It’s easy to see that $O$ must lie on the hypotenuse, otherwise it is not equidistant from all three vertices. Without loss of generality, assume that $b$ is the length of the hypotenuse. Then $\triangle AOB$ and $\triangle BOC$ are congruent isosceles triangles. Hence,

$\displaystyle 2\angle BAC+2\angle ACB=180^{\circ}\Longrightarrow\angle ABC=\angle BAC+\angle ACB=90^{\circ}$

Now suppose that the circumcenter $O$ is located outside the triangle. Without loss of generality, assume that $b$ is the length of the longest side of $\triangle ABC$. The arc subtended by the triangle $AOB$ is less than $180^{\circ}$, since $O$ is outside triangle $\triangle ABC$. Since $\triangle AOB$ and $\triangle COB$ are isosceles triangles, we see that

$\displaystyle 2\angle DOB +2\angle BOE+<180^{\circ}\Longrightarrow \angle AOD+\angle BOE<90^{\circ}$

Equivalently, $\angle ABC>90^{\circ}$ or $\triangle ABC$ is obtuse. $\Box$