CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Oct 2012
    Posts
    3

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

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    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

  3. #3
    Join Date
    Oct 2012
    Posts
    3

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

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

  4. #4
    Join Date
    May 2009
    Posts
    2,413

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

    Quote Originally Posted by enma View Post
    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.
    Last edited by nuzzle; October 12th, 2012 at 02:33 PM.

  5. #5
    Join Date
    Oct 2012
    Posts
    3

    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 .

  6. #6
    Join Date
    Oct 2008
    Posts
    1,456

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

    Quote Originally Posted by nuzzle View Post
    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 ) ?

  7. #7
    Join Date
    May 2009
    Posts
    2,413

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

    Quote Originally Posted by enma View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured