how to find the minimum covering radius for a set of scattered points

anyone can recommend any tool to do that?

thanks a lot

Hi there:

Im not sure but this post should go to Data Structures & Algorithms?

Anyway, a bound for this problem is to find the two farest points of the set. That is, the two points that are the most separated. Taking half that distance determines the radius of a circle that covers these two points and therefore any other point in the set -- as any other point is nearer --.

The rationale for this is that if exists another point that is outside this circle, its distance to at least one of the points determining the circle would be greater than the 2*radius and then you could use that distance [new point, old point] to determine a new radius, and then a new circle that covers the original points plus the new one.

I hope this works, or at elast can give you a starting point.

I might show my stupidity here but are you sure about this:

Quote:

---

Anyway, a bound for this problem is to find the two farest points of the set. That is, the two points that are the most separated. Taking half that distance determines the radius of a circle that covers these two points and therefore any other point in the set -- as any other point is nearer --.

---

Consider these three points: (-1, 0), (1, 0), (0, 1.1)
The two most seperated points should be (-1,0) and (1,0) the distance being 2.
According to the reasoning above the the radius of the circle should be 1. There is only one such circle that encloses (-1,0), (1,0) and that is the unit circle centered around origo. But (0,1.1) is outside the unit circle.

Like I said I may just be stupid.

An upper bound that would work in my eyes is radius of circle is the distance between the two most seperated point (same as your reasoning above except that no divide by 2). The circle is centered around one of the two most seperated points.

A trivial algorithm for finding a slightly better circle could be to traverse over the points randomly (as it feels like the ordering matters). When you pick a point you create new bounding circle that encloses both the point and previous bounding circle.

A slightly more advanced algorithm could be to use a modified A-* tree.

But I'm just guessing here. I'm sure lot of game developers out there are much more comfortable with using bounding circles/spheres than I am.

Simplex algorithm should do the trick.

You just need to minimise the function f(x, y), where f = the maximum distance from the point (x, y) to one of the points in the set (i.e. the radius of a circle centred at (x,y) that will cover all the points).

To find the smallest circle enclosing some points, try something like the following:

Code:

---

      int iXSum = 0;
      int iYSum = 0;
      for (vector<POINT>::const_iterator citer = points.begin();
        citer != points.end(); ++citer)
      {
        iXSum += (*citer).x;
        iYSum += (*citer).y;
      }
      center.x = int(double(iXSum)/double(points.size())+0.5);
      center.y = int(double(iYSum)/double(points.size())+0.5);

      radius = INT_MIN;
      for (vector<POINT>::const_iterator citer = points.begin();
        citer != points.end(); ++citer)
      {
        int iRadius = ceil(sqrt(pow(double(center.x-(*citer).x), 2.0) +
          pow(double(center.y-(*citer).y), 2.0)) + 0.5);
        if (iRadius > radius)
          radius = iRadius;
      }

---

center will contain the coordinates of the center of the circle and radius contains the radius.

Quote:

---

Originally Posted by marten_range

I might show my stupidity here but are you sure about this:

---

I may be stupid too :) but don't you just have to first find the bounding rectangle (the smallest rectangle that contains all points)? The diagonal of this rectangle will be the diameter of the smallest covering circle.

To find the bounding rectangle is easy. Just find the minimum and maximum x and y coordinates. The diagonal is then the line from (x_min, y_min) to (x_max, y_max). The length of this line is sqrt((y_max - y_min)^2 + (x_max - x_min)^2). This is also the diameter of the covering circle. Half it and you get the radius.

The centre of the covering circle is placed in the middle of the bounding rectangle which is the mid-point of the diagonal line calculated above.

Quote:

---

Originally Posted by _uj

I may be stupid too :) but don't you just have to first find the bounding rectangle (the smallest rectangle that contains all points)? The diagonal of this rectangle will be the diameter of the smallest covering circle.

To find the bounding rectangle is easy. Just find the minimum and maximum x and y coordinates. The diagonal is then the line from (x_min, y_min) to (x_max, y_max). The length of this line is sqrt((y_max - y_min)^2 + (x_max - x_min)^2). This is also the diameter of the covering circle. Half it and you get the radius.

The centre of the covering circle is placed in the middle of the bounding rectangle which is the mid-point of the diagonal line calculated above.

---

This isn't the smallest bounding circle. To see this, just draw 4 points in a cross-like manner and apply your algorithm to it.

Not only that but the center of the circle is not necessarily the same as the center of the bounding rectangle. Think about three points arranged like an L.

So Simplex seems to be the best method yet.

P.S. Marc, your solution doesn't work either. As an example, consider (-1,0), (0.9,0), (0.95,0), (1,0)

[moved the post to Algorithms]

This is actually a difficult problem, and is one special case of a general class of problems called "covering problems".

One widely quoted solution was proposed by Elzinga and Hearn in 1972: D. Jack Elzinga, Donald W. Hearn, "Geometrical Solutions for some minimax location problems," Transportation Science, 6, (1972), pp 379 - 394.

Here's a description of another algorithm from http://forums.wolfram.com/mathgroup/.../msg00486.html

Quote:

---

1) Take all pairs of points and calculate the minimal circle
covering each pair. (The radius of such a circle is just half
the distance between the pair of points, the center is the
midpoint between them.)

2) Take all triples of points and calculate the minimal circle
covering each triple. (That is just the circum circle.)

3) Throw away all circles which do not cover all points.

4) From the remaining circles take the one with the minimal
radius.

This algorithm guarantees to give the correct result.

---

The following site gives C source code which solves the problem in up to n-dimensional space: http://www2.inf.ethz.ch/personal/gaertner/miniball.html

Mike

Quote:

---

Originally Posted by Yves M

P.S. Marc, your solution doesn't work either. As an example, consider (-1,0), (0.9,0), (0.95,0), (1,0)

---

Yes you're right. My solution generates a bounding circle but not minimal...
Maybe an interesting working solution can be found at:
WmlContMinCircle2.h
WmlContMinCircle2.cpp

Quote:

---

Originally Posted by Marc G

This isn't the smallest bounding circle. To see this, just draw 4 points in a cross-like manner and apply your algorithm to it.

---

If you please would give me an example where my bounding circle wouldn't be minimal? You first define the bounding rectangle and then based on that the bounding circle. It seems logical to me but I am not a matematician. I would need a counter-example. Then I'll come up with something better.

Quote:

---

Originally Posted by Yves M

P.S. Marc, your solution doesn't work either. As an example, consider (-1,0), (0.9,0), (0.95,0), (1,0)

---

What about the following solution?

Code:

---

      double dBiggestDistance = DBL_MIN;
      for (int i=0; i<g_points.size(); ++i)
      {
        for (int j=i+1; j<g_points.size(); ++j)
        {
          double distance = sqrt(pow(g_points[j].x-g_points[i].x, 2.0) +
            pow(g_points[j].y-g_points[i].y, 2.0));
          if (distance > dBiggestDistance)
          {
            dBiggestDistance = distance;
            g_radius = dBiggestDistance / 2.0;
            g_center.x = (g_points[j].x + g_points[i].x) / 2.0;
            g_center.y = (g_points[j].y + g_points[i].y) / 2.0;
          }
        }
      }

---

Might not be the fastest way, but it certainly isn't slow either because of the way the second loop is written. It can be optimized a bit by calculating the g_center and g_radius after all the loops.

Quote:

---

Originally Posted by _uj

If you please would give me an example where my bounding circle wouldn't be minimal? You first define the bounding rectangle and then based on that the bounding circle. It seems logical to me but I am not a matematician. I would need a counter-example. Then I'll come up with something better.

---

Check the attached image.
The blue crosses are the 4 points I was talking about. The red rectangle is the bounding rectangle. The circle is not the minimal circle.

Quote:

---

Originally Posted by Marc G

Check the attached image.
The blue crosses are the 4 points I was talking about. The red rectangle is the bounding rectangle. The circle is not the minimal circle.

---

Thank you very much for your effort. I really appreciate this. :blush: At least my circle seems to be the outer bound of any solution meaning my circle is guaranteed to be covering.

Quote:

---

Originally Posted by MikeAThon

Here's a description of another algorithm from http://forums.wolfram.com/mathgroup/.../msg00486.html

---

May I add the step
0) Replace the set with the convex hull of the set. (complexity: O(n*ln(n)) )
It can lead to square rooting of number of points in common case and therefore the following n^3 finding the circle for tripples can become just n^1.5.