# Is this a wrong solution to the smallest enclosing circle problem?

I have a set of points in $\mathbb{R}^2$ and I need to find the smallest enclosing circle, i.e. the circle with the smallest radius that contains all of the points belonging to the set.

I have the following solution but I cannot prove its correctness or wrongness, I suspect it is wrong.

I find four points in the set:

$L=(x_L,y_L)$ has the smallest $x$ coordinate value,

$R=(x_R,y_R)$ has the largest $x$ coordinate value,

$B=(x_B,y_B)$ has the smallest $y$ coordinate value,

$T=(x_T,y_T)$ has the largest $y$ coordinate value.

$L$, $R$, $B$, $T$ stand for Left, Right, Bottom, Top.

Then for each of the four points I compute the distance to the other three points, for example I compute the distance from $L$ to $R$ like this

$d(L,R)=\sqrt{(x_L-x_R)^2+(y_L-y_R)^2}$

Now I have all the six distances: $d(L,R)$, $d(L,B)$, $d(L,T)$, $d(R,B)$, $d(R,T)$, $d(B,T)$.

I find the maximum distance of the six distances, let's call it $d(X,Y)$, and I say that the radius of the minimum enclosing circle is $\frac{d(X,Y)}{2}$ and its center is the midpoint of the segment $\overline{XY}$.

Is it a wrong solution? Why?

-
First of all, i'd say that points $L,R,B,T$ will not always be unique. –  barto Oct 6 '12 at 15:05

Your method does not work e.g. with the following points: $L(-4, 0)$, $T(0,3)$, $B(0,-3)$, $R(1,0)$. You would find $TB$ as the longest distance and take the circle with radius $3$ around $(0,0)$. But that does not contain $L$.

It cannot work in the first place if you only consider horizontal and vertical extension. For example take three vertices of a rotated equilateral triangle. Then the smallest circle for these three points is the circumscribed circle of the triangle. You may add more points inside the circle without changing that result. Especially, unless the angular position of the triangle is special, you can add points that make new top, bottom, left and right extremes, but are strictly inside the circle (make a sketch to see this); hence the top bottom etc. points cannot be used to fully determine the minimal radius. You might at best get a lower and an upper bound for the optimal radius.

-
thank you very much! –  Alessandro Jacopson Oct 6 '12 at 15:44

As shown in another answer, your linear-time method does not work in general. However, there are linear-time algorithms for the Smallest enclosing balls problem (linear in the number $n=|P|$ of the input points $P$, for a fixed dimension $d$, $P\subset\mathbb{R}^d$):

Note: If you are looking for an algorithm to compute the smallest enclosing ball of balls, you will find a C++ implementation of Matoušek, Sharir, and Welzl's LP-type algorithm in the Computational Geometry Algorithms Library (CGAL). (You do not need to use all of CGAL; simply extract the required header and source files.)

-
Thank you Hbf, I know your Miniball and I've already used it with pleasure. –  Alessandro Jacopson Apr 6 '13 at 16:42