aliassadi's blog

By aliassadi, history, 5 weeks ago, In English,

Hi.
I want to solve a problem. There is n points upper than x = 0 (not on x = 0). We can put circles with radius r on x axis (Which mean their center lie on x axis). We must use minimum circles to cover all points. a point is covered if lie on a circle or be inside a circle. in input n and n points and r is given.
Example:
Input:

3 2   // 3 point and r = 2    
1 2   // point 1    
-3 1  // point 2    
2 1   // point 3  

output:

2   

This is problem. We have one second time limit and we can not do lots of working.
I do a greedy approach. I start from most left. I choose from most left and choose a circle. my point should lie on that circle. I think this is best answer. then skip all point which covered with that circle and do it again until finish all point.
However I get wrong answer. I think a lot and I found some problem. I couldn't find a better way.
Is it possible to help me? I think that I can map this problem to a famous algorithm but I couldn't find it!!!
I'm sorry for bad English too. Thanks.

 
 
 
 

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If you're sorting points only by their x-coordinate, it may be that the leftmost point doesn't give you the leftmost circle that you need to place.

Say for example that you have a radius 100 and you have points (1, 1) and (2, 100). If you center your circle at (2, 0) it will cover both points, but if you consider (1, 1) first you'll place your circle somewhere between (98, 0) and (100, 0) and it will miss the second point.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. I found this problem. I changed my approach. same as before, I always after finishing covering with one circle, for next circle I start from left. but I didn't choose left point as a point which lies on circle. I go to right until there is a upper point (with higher y than before). after finding last point with this feature, I will choose that point. (to be on my circle) Then I test it to see, is it cover all before point? If yes, then I continue, otherwise, I skip that point and go one level before. I mean go to left, next point to this point and do same again.
    With this approach, for your example, when I go to right (because there is higher point), I will choose that point. after testing it, I will see that it will cover first point too. so I finish problem with only one circle.
    I didn't find any problem but I get some wrongs for this approach and I coudln't find why?!!
    Is it possible to help me? I'm so sorry for bad English.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use ternary search for x-coordinate of the minimal circle center.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain more? I read ternary search. I should read it's implementation more carefully but I understand it's purpose. however I couldn't find any map between this two problem.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you have the coordinates of the circle center as $$$(x_c,0)$$$ you can calculate the maximum distance from this point to all given points. This maximum distance would be the minimin radius of the circle having the center on $$$(x_c,0)$$$ and covering all given points:

      $$$\displaystyle r(x_c) = \max_{i} \sqrt{ (x_c - x_i)^2 + y_i^2 }$$$

      Choosing the value for $$$x_c$$$ according to the ternary search algorithm you can find the minimum radius for the covering circle.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh. I'm sorry. I think you think that we must choose r so cover all points however question is something else. I mentioned that: We must use minimum circles to cover all points. r is given to us with n points and we must find minimum circles with radius r on x axis with cover all of them.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, sorry. So you need to find minimum number of circles with fixed radius $$$r$$$. Then of course gready approach. Can the $$$y$$$-coordinate of some point be larger than $$$r$$$?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            No. all y-coordinate are smaller or equal to r. Question guarantee that for us.