help in a question : covering points with 2 circles

[nuzzle]

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.