how to find the minimum covering radius for a set of scattered points
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Member
Join Date
Jun 2004
Location
Holland
Posts
25

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

anyone can recommend any tool to do that?

thanks a lot

2. ## Re: how to find the minimum covering radius for a set of scattered points

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.

3. Member +
Join Date
Sep 2004
Posts
519

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

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.

4. ## Re: how to find the minimum covering radius for a set of scattered points

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

5. ## Re: how to find the minimum covering radius for a set of scattered 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);

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);
}```
center will contain the coordinates of the center of the circle and radius contains the radius.

6. _uj
Banned
Join Date
Nov 2003
Posts
1,405

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

Originally Posted by marten_range
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.
Last edited by _uj; December 1st, 2004 at 11:21 AM.

7. ## Re: how to find the minimum covering radius for a set of scattered points

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.

8. ## Re: how to find the minimum covering radius for a set of scattered points

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]

9. Elite Member Power Poster
Join Date
Nov 2002
Location
California
Posts
4,556

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

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

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

10. ## Re: how to find the minimum covering radius for a set of scattered points

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

11. _uj
Banned
Join Date
Nov 2003
Posts
1,405

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

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.

12. ## Re: how to find the minimum covering radius for a set of scattered points

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

13. ## Re: how to find the minimum covering radius for a set of scattered points

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.

14. _uj
Banned
Join Date
Nov 2003
Posts
1,405

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

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. At least my circle seems to be the outer bound of any solution meaning my circle is guaranteed to be covering.

15. ## Re: how to find the minimum covering radius for a set of scattered points

Originally Posted by MikeAThon
Here's a description of another algorithm from http://forums.wolfram.com/mathgroup/.../msg00486.html
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.
Last edited by RoboTact; December 4th, 2004 at 11:41 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•