Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
First of all, i'd say that points $L,R,B,T$ will not always be unique. –  barto Oct 6 '12 at 15:05
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
thank you very much! –  uvts_cvs Oct 6 '12 at 15:44
add comment

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.)

share|improve this answer
1  
Thank you Hbf, I know your Miniball and I've already used it with pleasure. –  uvts_cvs Apr 6 '13 at 16:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.