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 denote the vertices of a triangle in . We adopt the convention that denote the lengths of the sides opposite the vertices , respectively. We know that the circumscribed circle of the triangle exists and is unique, but where its center is located is uniquely determined by whether is acute, right, or obtuse. Furthermore, when the circumscribed circle coincides with the smallest enclosing circle is also uniquely determined by whether is acute, right, or obtuse.
Lemma 1. Given three points in in the plane, the point equidistant from all three is the intersection of the perpendicular bisectors of the sides of .
Proof. We know there exists a unique point equidistant from , so it suffices to show given two points , the locus of points equidistant from and is the span of the vector orthogonal to .
Suppose . I claim that . Indeed,
which shows that .
This lemma tells the geometer how to locate the circumcenter with a compass and ruler.
- The circumcenter is located in the interior of if and only if is acute.
- The circumcenter is located on the hypotenuse of if and only if is right.
- The circumcenter is located outside if and only if is obtuse.
(Images from Wikipedia)
Proof. Since acute, right, and obtuse are mutually exclusive, it suffices to prove only necessity in each statement. Define points by
Suppose the circumcenter is located in the interior. Since , , are isosceles (recall that is by definition equidistant from each vertex), we can write
where . Furthermore,
Hence, , which is equivalent to being acute.
Suppose the circumcenter is located on the boundary . It’s easy to see that must lie on the hypotenuse, otherwise it is not equidistant from all three vertices. Without loss of generality, assume that is the length of the hypotenuse. Then and are congruent isosceles triangles. Hence,
Now suppose that the circumcenter is located outside the triangle. Without loss of generality, assume that is the length of the longest side of . The arc subtended by the triangle is less than , since is outside triangle . Since and are isosceles triangles, we see that
Equivalently, or is obtuse.