Algorithm which is optimal for these geometry problems

  • Thread starter Moni
  • Start date
  • #1
Moni
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
arcnets
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
Moni
181
1
It seems Ok! But I need more general solution which can saisfy me :)
 

Suggested for: Algorithm which is optimal for these geometry problems

Replies
1
Views
278
Replies
38
Views
408
Replies
18
Views
345
Replies
9
Views
153
Replies
29
Views
755
  • Last Post
Replies
3
Views
419
  • Last Post
Replies
1
Views
435
  • Last Post
Replies
4
Views
525
Replies
1
Views
398
Top