Algorithm which is optimal for these geometry problems

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

Related Threads for: Algorithm which is optimal for these geometry problems

  • Posted
Replies
2
Views
2K
  • Posted
Replies
1
Views
622
Replies
1
Views
475
  • Posted
Replies
1
Views
2K
  • Posted
Replies
5
Views
2K
  • Posted
Replies
4
Views
1K
  • Posted
Replies
1
Views
1K
  • Posted
Replies
2
Views
346

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top