Finding smallest circle enclosing all points given their $x,y$-coordinates?

Question

I have an algorithm that I think calculates the minimum radius of all points in the list, which runs in $O(n)$ time and is incredibly easy to implement, but is it correct? If so, has it been invented before? It is not described on Wikipedia.

The algorithm, given a list of all points with $x,y$-coordinates, is as follows:

1. Get average of all $x$ and $y$ coordinates in the list in order to get the center of the circle $(\frac1n(x_1+x_2+\cdots+x_n), \frac1n(y_1+y_2+\cdots+y_n))$.
2. Calculate the distance between all the points from the center using $d((x_1,y_1), (x_2,y_2)) = \sqrt{(x_2 − x_1)^2 + (y_2 − y_1)^2}$, to find the point with maximum distance from the average point. So, this distance will be the minimum radius to cover all points.

Answer 1

Your algorithm is very simple because it doesn't always work.

Suppose we are given the points $(1,0)$, $(2,0)$, and $(6,0)$. Your algorithm will first average them to get the point $(3,0)$, then compute a maximum distance of $3$. However, a better solution is to take a circle with center $(3.5,0)$ and radius $2.5$.