CODEWITHSUNDEEP
algorithm
0xpentix
0xpentix

Reputation: 742

Understanding algorithm for finding the smallest circle enclosing points

At the moment I try to learn and understand geometric algorithms and I found the smallest-circle-problem quite interesting. I found many solutions and different algorithms including this one of which I'm not sure if it is Emo Welzl's.

However, I don't understand one specific (important) part:

  1. You're given N points on a (XY)-Plane.
  2. You order those points randomly
  3. Choose 3 points and create the circle where they are on the circle boundary.

  4. Get the next point and check if it is enclosed by the circle:

    a) If it is enclosed, repeat 4 until there are no more points left.

    b) If is not enclosed, create a new circle where the new point is on the circle boundary and still all other points are inside or on the circle.

Steps 1) to 4a) are simple, my problem is step 4b). How can I find this new circle? To me, it seems like this is the same problem just with a smaller (sub)set of points. (Divide-et-Impera)

I guessed I have to replace one of the 3 original points (the first 3 points, that made up the first circle) with the new point, but I'm not sure if this really works...

Upvotes: 2

Views: 7140

Answers (1)

Dese
Dese

Reputation: 348

From the 3 points A,B,C you can calculate the centre O of the circle: the point that is equidistant to those three. Its coordinates xO and yO are the means of xA,xB,xC and yA, yB, yC respectively.

Let's call D the 4th point, trace the circle of centre 0 and radius OD.

OD > OA (and OA=OB=OC) so A, B and C are in the circle.

EDIT

The solution I proposed above is not optimal.

I found a good explanation of Welzl's algorithm: see link

Of course, you can get his paper easily by looking on Google Scholar, but it is quite hard to read.

The basic principle is that in 4b) the circle is computed from all the possible circles having D on the boundary as well as two other points that were on the boundary before (or one point if that doesn't work and it will be diametrically opposed to D).

Upvotes: 1

Related Questions