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

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

One Response to Circumscribed Circle vs. Minimum Enclosing Circle II

  1. Pingback: Circumscribed Circle vs. Minimum Enclosing Circle III | 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