Algorithm which is optimal for these geometry problems

[Moni]

I don't know the optimal result but I gave some hint in that topic. Can anyone tell me the algorithm which is optimal for these geometry problems.

http://acm.uva.es/board/viewtopic.php?t=2631

 

[arcnets]

Hi Moni,
I think the circle problem is interesting, the other one not so.
My approach would be trial & error. To have a finite number of trials, use a grid where the circle centers can be.
To place the 1st circle, try all center positions in the grid and find the one that covers the most points. To place the 2nd circle, find the center position that has the largest number of additional points covered. Go on like this, till all points are covered.
Next step, you refine the grid. See if anything spectacular happens. I doubt it will.
Of course, the problem is trivial if all points are more than 2r apart. Then minimum number of circles = number of points. That's the trivial case. If points are slightly denser, my algorithm will become ambiguous and so, will not work. But I believe it will be optimal when points are very dense. Any comments?

 

[Moni]

It seems Ok! But I need more general solution which can saisfy me :)