Jung’s Theorem: Enclosing a Set of Points

Let us imagine that we have a finite set ${P}$ of points in the plane ${\mathbb{R}^2}$ (Fig. 1a). How large a circle is required to enclose them. More specifically, what is the minimum radius of such a bounding circle? The answer is given by Jung’s Theorem.

Left: a set P of points in the real plane. Right: The span s is the maximum distance between two points of P.

We define the span ${s(P)}$ to be the largest distance between any two points of ${P}$ :

$latex s(P) = \mathrm{max} || p – q || \qquad\mbox{for}\qquad p, q \in P &fg=000000$

(see Fig. 1b). This is often called the diameter of the set, but we use the alternative term span to avoid confusion with the diameter of the circle that is about to appear.

Jung’s Theorem assures us that there is a circle containing all the points of ${P}$ within it or on it, with radius ${r}$ satisfying

$\displaystyle r \le \frac{s}{\sqrt{3}} \qquad\qquad (1)$

Left: the smallest circle enclosing ${P}$ . Right: The radius of the circle satisfies ${r\le s/\sqrt{3}}$ .

Left: the smallest circle enclosing ${P}$ . Right: The radius of the circle satisfies ${r\le s/\sqrt{3}}$ .

Although Jung’s Theorem gives an upper bound on the circle radius for a given span ${s}$ , a smaller circle will often do; for example, if all the points in ${P}$ lie on a straight line then, clearly, ${r = s/2}$ . However, if ${P}$ is an equilateral triangle of side ${s}$ , then ${r = s / \sqrt{3}}$ , the radius of the circumcircle, so no better bound than (1) can be found.

Generalization

The theorem has been extended to higher dimensions. Suppose ${K}$ is a compact set in ${\mathbb{R}^n}$ . Compactness in a Euclidean space means boundedness, so there is an ${(n-1)}$ -dimensional sphere ${\mathbb{S}}$ enclosing the set: ${K \subset \mathbb{S}}$ . As before, we define the span ${s}$ of ${K}$ to be the largest distance between any two points of ${K}$ . Then Jung’s theorem ensures that there exists a closed ball ${B}$ with radius ${r}$ satisfying

$\displaystyle r \leq s{\sqrt {\frac {n}{2(n+1)}}} \qquad\qquad (2)$

such that ${K\subset B}$ . Just as an equilateral triangle in the plane requires ${r = s/\sqrt{3}}$ , the limiting value here is required for a regular ${n}$ -simplex.

More generally, for any bounded set ${S}$ in any metric space, ${s/2 \leq r \leq s}$ . The theorem has also been extended to spaces with non-Euclidean geometries.

Heinrich Jung

Heinrich Jung was born in Essen in 1876. He studied mathematics, physics and chemistry in Marburg and Berlin. His teachers included mathematicians Kurt Hensel, Lazarus Fuchs and Georg Frobenius and physicist Max Planck. He received his doctorate under Friedrich Hermann Schottky in 1899, with a dissertation entitled: On the smallest sphere that encloses a spatial figure.

Heinrich Wilhelm Ewald Jung (1876–1953).

In 1902, Jung completed his habilitation in Marburg, and lectured there until 1908. In 1913, he was appointed full professor in Kiel. After a period of military service, he moved in 1920 to the University of Halle, where he remained for the rest of his career, retiring in 1948. Jung supervised 19 doctoral students during his career.

In his doctoral dissertation, Jung determined the smallest possible radius of an ${(n-1)}$ -dimensional sphere enclosing a given set of points points in ${n}$ -dimensional space. For two and three dimensional space, the solution is obtained geometrically.

According to his Wikipedia page, Jung’s fame derives mainly from his arithmetic theory of algebraic functions in two variables. This theory is presented in his book Einführung in die algebraische Theorie der Funktionen von zwei Veränderlicher (Introduction to the algebraic theory of the functions of two variables).

Sources

${\bullet}$ Jung, Heinrich, 1901: On the smallest sphere that encloses a solid figure. Doctoral Dissertation, Marburg 1899, reprinted in J. Reine Angew. Math. (Crelle’s Journal), 123, 241–257.

${\bullet}$ Heinrich Jung. Wikipedia.

${\bullet}$ Smallest-circle Problem. Wikipedia.

ThatsMaths