24 Smallest Enclosing Disk via Randomized Algorithms

Lecture from: 20.05.2025 | Video: Homelab

In this lecture, we study a classic geometric optimization problem and a strikingly elegant randomized algorithm to solve it in expected linearithmic time. The algorithm, originating from work by Clarkson, illustrates powerful ideas in randomized geometric optimization and probabilistic analysis.

The SmallEnclDisk Problem

Given a finite point set $P \subseteq R^{2}$ , determine the closed disk of minimal radius that contains all points in $P$ .

We define:

A disk $C$ with center $z$ and radius $r$ as:
$C = {x \in R^{2} : ∥ x - z ∥ \leq r}$
The disk $C$ is said to enclose $P$ if:
$P \subseteq C$
This disk is called the smallest enclosing circle $C (P)$ if it has the smallest possible radius among all such enclosing disks.

Lemma: Uniqueness of the Smallest Enclosing Circle

For every finite point set $P \subseteq R^{2}$ , there exists a unique smallest enclosing circle $C (P)$ .

Proof sketch:

Suppose two distinct disks $C_{1}, C_{2}$ both minimally enclose $P$ , with equal radius $r$ but centers $z_{1} \neq = z_{2}$ .
Let $z = \frac{1}{2} (z_{1} + z_{2})$ be the midpoint.
Construct a disk centered at $z$ passing through the intersection points of $C_{1}, C_{2}$ .
This new disk strictly contains $C_{1} \cap C_{2}$ and has smaller radius than $r$ - contradiction.

Hence, the smallest enclosing disk is uniquely defined.

Lemma: 3-Point Certificate

For $∣ P ∣ \geq 3$ , there exists a subset $Q \subseteq P$ , $∣ Q ∣ \leq 3$ , such that:

C (Q) = C (P)

That is, the smallest enclosing circle is determined by at most 3 boundary points. These 3 points form a minimal certificate of the optimal solution.

Intuitively:

If $C (P)$ contains all of $P$ , and any point lies in the interior, it’s not necessary to determine the boundary.
Only up to 3 points (due to geometry of circles) can lie on the boundary and determine the unique minimal disk.

Basic Algorithms

Complete Enumeration

Enumerate all 3-subsets $Q \subseteq P$ . For each:

Compute $C (Q)$
Check whether $P \subseteq C (Q)$

There are $(3 n) = O (n^{3})$ candidates.
Each check takes $O (n)$ .
Total time: $O (n^{4})$

Smarter Enumeration

Instead of checking containment, track the candidate with largest radius:

Still iterate over $(3 n)$ subsets.
Keep best disk seen so far.

Runtime: $O (n^{3})$
Still inefficient for large $n$

A First Randomized Algorithm

Expected trials: $\leq (3 n) = O (n^{3})$ since probability of correctly selecting the points in one sample is $\frac{1}{( 3 n )}$ and this is a geometric distribution.
Each trial: $O (n)$ check
Total expected runtime: $O (n^{4})$

This naive approach lacks adaptivity: it doesn’t learn from previous failures. But the insight that “bad points” (outside current disk) matter more leads to improvement.

Clarkson’s Randomized Algorithm

We maintain a multiset $P^{'}$ initialized as $P$ , and evolve it by amplifying the influence of points that prevent current samples from enclosing the set.

Sample is drawn from $P^{'}$ , which changes over time.
Violating points (outside current disk) become more likely in future samples.
Idea resembles a multiplicative weights update method - emphasizing “important” points.

Why It Works

Let $B^{*} \subseteq P$ be the set of at most 3 points that define the optimal disk: $C (B^{*}) = C (P)$ .

If current disk fails: at least one point in $B^{*}$ is outside.
Each time we fail, at least one such point is doubled.
After $k$ rounds, some point in $B^{*}$ must appear $\geq 2^{k /3}$ times.
Hence, $∣ P^{'} ∣ \geq 3 \cdot 2^{k /3}$

But we can also bound expected size of $P^{'}$ from above.

Growth Upper Bound

Let $X_{k}$ be the size of $P^{'}$ after $k$ rounds. Then:

E [X_{k}] \leq (1 + \frac{3}{r + 1})^{k} n

For $r = 11$ , this becomes $(\frac{5}{4})^{k} n$

Since $2^{1/3} \approx 1.26 > 1.25$ , these bounds must eventually conflict → the process must terminate in $O (lo g n)$ rounds.

Sampling Lemma

This key lemma bounds expected number of points outside disk defined by random sample.

Let $P^{'}$ be a multiset of size $N$ , and $R \subseteq P^{'}$ be a uniform random sample of size $r$ . Then:

E [∣ P^{'} ∖ C (R) ∣] \leq \frac{3 ( N - r )}{r + 1}

Intuition:

A point $p \in / C (R)$ implies that $p$ is “essential” for any superset.
But at most 3 such essential points per subset.

Proof sketch: Define indicator functions:

$out (p, R) = 1$ if $p \in / C (R)$
$ess (p, Q) = 1$ if $C (Q ∖ {p}) \neq = C (Q)$

Connect expected number of outs to essentiality and count via combinatorics.

Look at the proof below, I didn’t fully get it…

Final Runtime Analysis

Let $T$ be the number of rounds until success.

We showed:

$E [X_{k}] \leq (5/4)^{k} n$
But if $T \geq k$ , then $∣ P^{'} ∣ \geq 3 \cdot 2^{k /3}$

Set $k_{0} = ⌈ - lo g_{0.993} n ⌉$ . For $k > k_{0}$ , the probability that algorithm hasn’t terminated is very small.

Finally, the expected number of rounds is:

E [T] = k = 1 \sum \infty Pr [T \geq k] \leq k_{0} + O (1) = O (lo g n)

Total expected runtime:

O (n \cdot E [T]) = O (n lo g n)

Conclusion

Theorem

The randomized algorithm computes the smallest enclosing circle of $P \subseteq R^{2}$ in expected time $O (n lo g n)$ .

Summary

The method generalizes to enclosing balls (or ellipsoids) in fixed higher dimensions with modified constants.
Other linear-time randomized and deterministic methods exist, but Clarkson’s approach is notable for its “simplicity” and analysis.

Concept	Insight
Smallest enclosing circle	Determined by ≤ 3 points on boundary
Randomized sampling	Likely to hit defining points after boosting their multiplicity
Geometric sensitivity	Points outside a sampled disk are crucial - “they teach us something”
Sampling lemma	Shows expected number of offending points is small
Multiplicative biasing	Drives convergence by boosting important point probability

Continue here: 25 Convex Hulls - Geometry, Algorithms, and Complexity

CS Notes

Explorer