Minimum encompassing circle and ellipse

This is again about finding the smallest geometric shape containing all our data points. Here I focus on easy, convex cases: a circle and an ellipse. After the last post, where I was struggling mightily with a non-convex version of this model, this should be a breeze. First let's do circles.

1. Minimum encompassing circle

This looks like a very easy problem to formulate and solve, not worth spending much time on. I think there are some interesting angles, you may not have thought about before.

Given \(n\) points \({\color{darkblue}p}_i\) (with their \(x\) and \(y\) coordinates), find the smallest circle identified by it center coordinates \({\color{darkred}c}\) and its radius \({\color{darkred}r}\), by minimizing \({\color{darkred}r}\), under the constraint that all points \({\color{darkblue}p}_i\) are inside the circle.

Smallest circle model
\[\begin{align}\min_{{\color{darkred}r},{\color{darkred}c}}\> & {\color{darkred}r} \\ & {\bf{dist}}({\color{darkblue}p}_i,{\color{darkred}c}) \le {\color{darkred}r} && \forall i\\ & {\color{darkred}r}\ge 0 \\ & i \in \{1,\dots,n\} \end{align}\]