Smallest Enclosing Disk

Overview

Given a finite point set $P\subseteq {\mathbb{R}}^2$, we want to determine the closed disk of minimal radius that contains all points in $P$. A disk $C$ with center $z\in {\mathbb{R}}^2$ and radius $r\ge 0$ is defined as: $C=\{x\in {\mathbb{R}}^2:\Vert x-z\Vert \le 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

NOTE

The smallest enclosing circle $C(P)$ is unique ($|P|\ge 3$)

NOTE

Let $|P|\ge 3$, then there exists a subset $Q\subseteq P$ with $|Q|\le 3$ such that $C(Q)=C(P)$

Naive solution