Circumscribed Circle vs. Minimum Enclosing Circle I

In the introduction to Jung’s theorem, we proved the existence of a unique ball of minimal radius enclosing a given set bounded set S\subset\mathbb{R}^{d}. This ball is called the minimum enclosing ball, or in the special case d=2, the smallest circle. Related to, but nevertheless distinct, is another enclosing circle call the circumscribed circle. Given non-collinear distinct points A, B, C\in\mathbb{R}^{2}, there exists a unique circle circumscribing the triangle with vertices A, B, and C. Not surprisingly, this circle is called the circumscribed circle or circumcircle of the triangle \triangle ABC, its center is called the circumcenter, and its radius is called the circumradius. The definition of the circumcircle can be generalized to arbitrary polygons, although it need not exist, but we will restrict our attention to triangles.

My motivation for discussing the circumcircle in conjunction with smallest circle and Jung’s theorem is to establish when the circumcircle and smallest circle are distinct, and how we can use the geometric properties of the circumcircle to create efficient algorithms for the computation of the smallest circle. In particular, that the smallest circle is characterized by at least two and at most three points.

Let’s first show existence and uniqueness by explicitly computing the circumcenter and circumradius.

Theorem. Given A,B,C\in\mathbb{R}^{2} as above, there exists a unique circle circumscribing the triangle with vertices A, B, and C.

Proof. Suppose the circumscribed circle exists with center u\neq0 and radius r>0. Then, for any point of the circle v, we have

\displaystyle\left\|v-u\right\|^{2}=r^{2},\indent\left\|A-u\right\|^{2}=r^{2},\indent\left\|B-u\right\|^{2}=r^{2},\indent\left\|C-u\right\|^{2}=r^{2}

Applying the polarization identity to the standard inner product, we have

\displaystyle\left\|v\right\|^{2}+\left\|u\right\|^{2}-2(u_{1}v_{1}+u_{2}v_{2})-r^{2}=0,

which is equivalent to the equation

\displaystyle\left\|v\right\|^{2}\left(\frac{u_{1}}{\left\|u\right\|^{2}}+\frac{u_{2}}{\left\|u\right\|^{2}}\right)-2\frac{u_{1}}{\left\|u\right\|^{2}}v_{1}-2\frac{u_{2}}{\left\|u\right\|^{2}}v_{2}-r^{2}=0

Completely analogous equations hold where \left\|v\right\|^{2} is replaced by \left\|A\right\|^{2},\left\|B\right\|^{2},\left\|C\right\|^{2}, respectively. Define real numbers

\displaystyle x_{1}:=\left\|u\right\|^{-2},\indent x_{2}:=\frac{u_{1}}{\left\|u\right\|^{2}},\indent x_{3}:=\frac{u_{2}}{\left\|u\right\|^{2}},\indent x_{4}:=1-\frac{r^{2}}{\left\|u\right\|^{2}}

We can summarize the four equations with the matrix equation

\displaystyle\begin{bmatrix}\left\|v\right\|^{2}&-2v_{1}&-2v_{2}&1\\ \left\|A\right\|^{2}&-2A_{1}&-2A_{2}&1\\ \left\|B\right\|^{2}&-2B_{1}&-2B_{2}&1\\ \left\|C\right\|^{2}&-2C_{1}&-2C_{2}&1\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}=\begin{bmatrix}0\\ 0\\ 0\\ 0\end{bmatrix}

We see that the existence of the circumscribed circle is equivalent to a nontrivial solution to this matrix equation. Since the matrix is square, the existence of a nontrivial solution is equivalent to the matrix having zero determinant. Hence,

\begin{array}{lcl}\displaystyle0&=&\displaystyle\begin{vmatrix}\left\|v\right\|^{2}&v_{1}&v_{2}&1\\ \left\|A\right\|^{2}&A_{1}&A_{2}&1\\ \left\|B\right\|^{2}&B_{1}&B_{2}&1\\ \left\|C\right\|^{2}&C_{1}&C_{2}&1\end{vmatrix}\\[.9 em]&=&\displaystyle\left\|v\right\|^{2}\begin{vmatrix}A_{1}&A_{2}&1\\B_{1}&B_{2}&1\\C_{1}&C_{2}&1\end{vmatrix}-v_{1}\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}+v_{2}\begin{vmatrix}\left\|A\right\|^{2}&A_{1}&1\\ \left\|B\right\|^{2}&B_{1}&1\\ \left\|C\right\|^{2}&C_{1}&1\end{vmatrix}-\begin{vmatrix}\left\|A\right\|^{2}&A_{1}&A_{2}\\ \left\|B\right\|^{2}&B_{1}&B_{2}\\ \left\|C\right\|^{2}&C_{1}&C_{2}\end{vmatrix}\\[.9 em]&=&\displaystyle\begin{vmatrix}A_{1}&A_{2}&1\\B_{1}&B_{2}&1\\C_{1}&C_{2}&1\end{vmatrix}\left(v_{1}-\frac{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}{\begin{vmatrix}A_{1}&A_{2}&1\\B_{1}&B_{2}&1\\C_{1}&C_{2}&1\end{vmatrix}}\right)^{2}+\left(v_{2}-\frac{\begin{vmatrix}A_{1}&\left\|A\right\|^{2}&1\\B_{1}&\left\|B\right\|^{2}&1\\C_{1}&\left\|C\right\|^{2}&1\end{vmatrix}}{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}\right)^{2}\\[.9 em]&-&\displaystyle\frac{{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}^{2}+{\begin{vmatrix}A_{1}&\left\|A\right\|^{2}&1\\B_{1}&\left\|B\right\|^{2}&1\\C_{1}&\left\|C\right\|^{2}&1\end{vmatrix}}^{2}}{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}-\begin{vmatrix}\left\|A\right\|^{2}&A_{1}&A_{2}\\ \left\|B\right\|^{2}&B_{1}&B_{2}\\ \left\|C\right\|^{2}&C_{1}&C_{2}\end{vmatrix}\end{array}

But this is the equation of a circle with center s described by coordinates

\displaystyle s_{1}=\frac{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}{\begin{vmatrix}A_{1}&A_{2}&1\\B_{1}&B_{2}&1\\C_{1}&C_{2}&1\end{vmatrix}},\indent s_{2}=\frac{\begin{vmatrix}A_{1}&\left\|A\right\|^{2}&1\\ B_{1}&\left\|B\right\|^{2}&1\\ C_{1}&\left\|C\right\|^{2}&1\end{vmatrix}}{\begin{vmatrix}A_{1}&A_{2}&1\\B_{1}&B_{2}&1\\C_{1}&C_{2}&1\end{vmatrix}}

and radius r^{2} described by

\displaystyle r^{2}=\frac{{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}^{2}+{\begin{vmatrix}A_{1}&\left\|A\right\|^{2}&1\\B_{1}&\left\|B\right\|^{2}&1\\C_{1}&\left\|C\right\|^{2}&1\end{vmatrix}}^{2}}{\begin{vmatrix}\left\|A\right\|^{2}&A_{2}&1\\ \left\|B\right\|^{2}&B_{2}&1\\ \left\|C\right\|^{2}&C_{2}&1\end{vmatrix}}+\begin{vmatrix}\left\|A\right\|^{2}&A_{1}&A_{2}\\ \left\|B\right\|^{2}&B_{1}&B_{2}\\ \left\|C\right\|^{2}&C_{1}&C_{2}\end{vmatrix}

Note that we know that the denominator is nonzero by hypothesis that A,B,C are not collinear. These explicit formulae prove the uniqueness of the circumcircle. Working backwards, we see that either the center of the circumscribed circle is the origin and the radius is \left\|A\right\|^{2}=\left\|B\right\|^{2}=\left\|C\right\|^{2} or the center is s and the radius is r. \Box

Advertisements
This entry was posted in cs.DS, math.OC and tagged , , , . Bookmark the permalink.

One Response to Circumscribed Circle vs. Minimum Enclosing Circle I

  1. Pingback: Circumscribed Circle vs. Minimal Enclosing Circle II | Math by Matt

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s