
October 11th, 2012, 11:15 AM
#1
help in a question : covering points with 2 circles
I've been given the next question but i am having truble with it .
we r given n points on the plane , and we need to find 2 circles that will cover all the points, while the the radius of the larger one is the minimum possible. (so we cant say we will take a very large circle).
we need to do it in O(n^7).
can som 1 tell me an answer to this problem? or even a known algorithm that close to it .
ive been thinking about this problem for 3 days and i cant think about anything..

October 12th, 2012, 07:22 AM
#2
Re: help in a question : covering points with 2 circles
Do you need an exact answer is is an approximation OK too?
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

October 12th, 2012, 07:50 AM
#3
Re: help in a question : covering points with 2 circles
Anyhting will b ok, if u have an idea i'll take it.

October 12th, 2012, 09:15 AM
#4
Re: help in a question : covering points with 2 circles
Originally Posted by enma
Anyhting will b ok, if u have an idea i'll take it.
I have an idea but it's O(N^6) so it's probably wrong . I give it without proof and without much detail so you can mull it over yourself.
Using 3, 2 or 1 point(s) you can define a minimal circle. In the first case the three points will be somewhere on the circle circumferense. In the second case the two points will be on the circumference diametrically opposite each other. In the third case the circle has degenerated to the centre point (but one can still think of it as a circle only with infinitesimally small diameter). With 4 points or more a circle is overdetermined. Any combination of 3, 2 and 1 points will determine a minimal circle and the other points will be either inside or outside such a circle.
For the problem you generate all possible 3, 2 and 1 minimal circles from the N points. The number of 3circles will be proportional to N^3. The number of 2circles will be proportional to N^2 and the 1circles will be exactly N. So all together the number of circles M will be proportional to N^3 + N^2 + N which means O(N^3) complexity.
Now you have all possible M minimal circles and it's just to find the best pair of circles which together cover all N points. So all M circles are paired up with all other M circles which is an O(M^2) operation and since M is proportional to O(N^3) points the total becomes O((N^3)^2). That's O(N^6) where N is the number of points.
I forgot one operation. For each minimal circle you need to determine which of the N points lie inside. Otherwise you cannot decide whether a circle pair covers all points. That's an additional O(N) operation so the total actually becomes O(N^7) as suggested.
Last edited by nuzzle; October 12th, 2012 at 02:33 PM.

October 12th, 2012, 11:19 AM
#5
Re: help in a question : covering points with 2 circles
Originally Posted by nuzzle
In the first case the three points will be somewhere on the circle circumferense.
correct me if I'm wrong, but the task is to find a pair of circles of which the bigger has minimal radius; so, in the three points case the solution is the circle centered in the middle point of and having the diamater equal to the distance between the nearest pair of points; the other circle has 0radius and is centered in the remaining point. The one and two points cases give a pair of 0radius circles.
however, as in nuzzle reasoning, for N>=3 such a minimal circle will always be uniquely determined by passing through 3 or 2 points ( the 2points case giving a circle centered in their middle point ).
Hence, I think the correct solution is to traverse all possible triples along with their subpairs, checking that the resulting circle has a radius smaller than the radius of the bounding circle of the points outside of it, and finally taking the minimal one. The problem is that this is O(N^4) ... so, is there any other requirement on the second circle ( or am I missing something ) ?

October 12th, 2012, 10:16 AM
#6
Re: help in a question : covering points with 2 circles
The algorithm u proposed is somthing i was thinking too, but i wasnt sure about it.
I think ur answer is ok, ty for the help .

October 12th, 2012, 12:04 PM
#7
Re: help in a question : covering points with 2 circles
Originally Posted by enma
I think ur answer is ok
Well, I can prove it's correct.
You only have to show that the optimal pair of circles is to be found among the set of minimal circles (*) (and not just any circles). And that's easy. Say you have any circle that's not minimal and is covering some points. Then you can always shrink it to become a minimal circle still covering the same points. And since this circle was shrunk it's a better choise than the original circle. It follows that only minimal circles need be considered. So if you exhaustively consider every possible pair of minimal circles you're guaranteed to find the optimal pair(s).
(*) A minimal circle is a 3, 2 or 1 point circle as defined in my previous reply.
Last edited by nuzzle; October 12th, 2012 at 01:19 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

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
