📂Topological Data Analysis

Welzl Algorithm: Solution to Smallest Enclosing Disk Problem

Problem

Smallest Enclosing Disk

Let’s denote it as $n > d$. In a $d$-dimensional Euclidean space, given a finite set $P = \left\{ p_{k} \right\}_{k=1}^{n} \subset \mathbb{R}^{d}$, the following optimization problem is referred to as the Smallest Enclosing Disk Problem: $$ \begin{matrix} \text{Minimize} & r \ge 0 \\ \text{subject to} & \left\| c - p_{k} \right\|_{2} \le r \end{matrix} \\ c \in \mathbb{R}^{d} , k = 1, \cdots , n $$

Tips

Here are some useful facts about this problem, though they may not be grand enough to be called theorems:

• If $P$ are affinely independent, the disk’s boundary will contain between $2$ and $d+1$ points from $P$. Simply put, unless the points overlap or more than two lie on the same line, exactly $2 \le m \le d+1$ points uniquely determine the smallest enclosing disk.
  • For example, in a $d = 2$-dimensional plane, a circle is uniquely determined by exactly three points.
• Generally, when $n > d+1$ points are given, it is believed to be impossible to find an explicit formula, not an algorithm, to solve this problem. The points that uniquely determine the smallest enclosing disk on the boundary are called supports, and it’s impossible to identify the supports just by looking at the points.
  • The concept of points on the boundary being called supports is common in geometric problems. In Support Vector Machines, the supports refer to the points on the boundary.
• Therefore, developing an algorithm to solve this problem essentially means ensuring or finding a quick way to identify the boundary supports. However, the fundamental idea of the current algorithms is almost based on Welzl’s concept, and they are collectively referred to as the Welzl Algorithm¹, with subsequent studies following this lineage.

Solution

Welzl’s Algorithm ²

Welzl’s Algorithm is a recursive solution to the smallest enclosing disk problem. It fundamentally involves adding and removing points one by one to find supports, and repeating this process to ensure the disk obtained encompasses all given points.

When $n \le d+1$ points are given, finding a disk that exactly encloses them is relatively simple, so we assume such a function exists. Though in actual implementation, this may not be as straightforward, the crux of the smallest enclosing disk problem lies elsewhere.

Pseudocode ³

$(c,r)$ = welzl$\left( P, S \right)$

• Input: Receives a set of given points $P = \left\{ p_{k} \right\}_{k=1}^{n} \subset \mathbb{R}^{d}$ and a set of candidate supporters $S \subset P$. As mentioned in the tips, $\left| S \right| \le d+1$ holds.
• Output: Obtains a tuple $(c,r)$ of the center $c$ and radius $r$ of the smallest disk enclosing all points of $P$. Let’s denote the closed ball with center $c$ and radius $r$ as $D = B \left[ c,r \right]$.

$(c,r)$ = trivial$\left( S \right)$

• Input: Receives a set of points $S \subset P$ where $\left| S \right| \le d+1$ holds.
• Output: Obtains a tuple $(c,r)$ of the center $c$ and radius $r$ of the smallest disk enclosing all points of $S$. Assuming trivial is simpler than welzl, its pseudocode is not provided separately.

---

function welzl$\left( P, S \right)$
　　$S := \emptyset$
　　if $P = \emptyset$ or $\left| S \right| = d+1$ then
　　　　return trivial$\left( S \right)$
　　else
　　　　choose $p \in P$
　　　　$D := $ welzl$\left( P \setminus \left\{ p \right\}, S \right)$
　　　　if $p \in D$ then
　　　　　　return $D$
　　　　end if
　　end if
　　return welzl$\left( P \setminus \left\{ p \right\} , S \cup \left\{ p \right\} \right)$
end function

---

welzl is written as a recursive function, meaning the calculation begins with trivial. The appearance of choose in the pseudocode of welzl as choose $x \in X$ indicates randomly selecting an element $x$ from the set $X$.

If you understand that returning welzl$\left( P \setminus \left\{ p \right\} , S \cup \left\{ p \right\} \right)$ at the end signifies the process of finding supports by sequentially removing points from $P$ and adding them to $S$, then you have essentially grasped the algorithm.

Explanation

Let’s unpack the constraints of the smallest enclosing disk. Finding $c$ and $r$ that satisfy $\left\| c - p_{k} \right\|_{2} \le r$ means finding a center $c$ and radius $r$ that can at least enclose all given points. However, since the Euclidean space is vast, these constraints can always be met by arbitrarily choosing $r$ as long as $c$ is fixed. Naturally, our interest lies in minimizing $r$, i.e., finding the smallest ball that encloses the given points.

The Issue with Simplification

Enclosing is not a widely used term across mathematics, but using enclosing directly in translation felt too lengthy and abstract, hence the chosen term. Initially, enclosing itself isn’t overwhelmingly more common than bounding. Moreover, the term disk is used here to mean a closed ball, but in English, terms like ball or sphere are also frequently used. Let’s not get too hung up on each word and its translation.

History

An early solution based on linear programming was known through Raimund Seidel.

In 1991, Emo Welzl proposed a recursive algorithm in his paper, setting a new standard, the so-called SOTA (State Of The Art), for the smallest enclosing disk problem. As of 2022, Welzl’s algorithm is still known to be the best for the general smallest enclosing disk problem, with many subsequent studies improving upon it.

In 1999, Bernd Gärtner improved upon Welzl’s algorithm by incorporating applications of quadratic programming, making his approach more efficient.⁴ His implementation, written in C++, can be seen on the ETH Zurich website⁵.

In 2003, Kaspar Fischer introduced the use of the simplex method from linear programming and the Bland’s rule to write faster code,⁶ and in 2013, Thomas Larsson proposed a method that, while approximate, boasted speed and robustness.⁷

The research introduced thus far can be seen to follow a major lineage from Welzl to Gärtner to Fischer upon reviewing their references.

Applications

A notable application of Welzl’s algorithm is the construction of Čech complexes.