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.
Re: how to find the minimum covering radius for a set of scattered points
I might show my stupidity here but are you sure about this:
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.
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).
Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
-- Sutter and Alexandrescu, C++ Coding Standards
Programs must be written for people to read, and only incidentally for machines to execute.
-- Harold Abelson and Gerald Jay Sussman
The cheapest, fastest and most reliable components of a computer system are those that aren't there. -- Gordon Bell
Re: how to find the minimum covering radius for a set of scattered points
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.
Last edited by _uj; December 1st, 2004 at 12:21 PM.
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.
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]
Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
Supports C++ and VB out of the box, but can be configured for other languages.
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.
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.
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
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.
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.
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.
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.
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.
Last edited by RoboTact; December 5th, 2004 at 12:41 AM.
"Programs must be written for people to read, and only incidentally for machines to execute."