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.. :confused:

Re: help in a question : covering points with 2 circles

Do you need an exact answer is is an approximation OK too?

Re: help in a question : covering points with 2 circles

Anyhting will b ok, if u have an idea i'll take it.

Re: help in a question : covering points with 2 circles

Quote:

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 3-circles will be proportional to N^3. The number of 2-circles will be proportional to N^2 and the 1-circles 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.

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

Re: help in a question : covering points with 2 circles

Quote:

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 0-radius and is centered in the remaining point. The one and two points cases give a pair of 0-radius 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 2-points case giving a circle centered in their middle point ).

Hence, I think the correct solution is to traverse all possible triples along with their sub-pairs, 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 :) ) ?

Re: help in a question : covering points with 2 circles

Quote:

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.