Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm which is optimal for these geometry problems

  1. Apr 20, 2003 #1
    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 [Broken]
    Last edited by a moderator: May 1, 2017
  2. jcsd
  3. Apr 21, 2003 #2
    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?
  4. Apr 23, 2003 #3
    It seems Ok! But I need more general solution which can saisfy me :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook