Algorithm which is optimal for these geometry problems

  • Thread starter Moni
  • Start date
  • #1
181
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:

Answers and Replies

  • #2
508
0
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?
 
  • #3
181
1
It seems Ok! But I need more general solution which can saisfy me :)
 

Related Threads on Algorithm which is optimal for these geometry problems

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
690
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
1K
Replies
4
Views
924
  • Last Post
Replies
2
Views
417
Replies
2
Views
689
  • Last Post
Replies
3
Views
3K
Top