Algorithm which is optimal for these geometry problems

In summary, Moni is looking for an algorithm to solve geometry problems, specifically the circle problem. Another person suggests using a trial and error approach and refining the grid to find the optimal solution. However, they mention that the algorithm may not work if the points are too dense. Moni is still looking for a more general solution.
  • #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:
Mathematics news on Phys.org
  • #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?
 
  • #3
It seems Ok! But I need more general solution which can saisfy me :)
 

1. What is an algorithm for geometry problems?

An algorithm for geometry problems is a step-by-step procedure or set of rules that can be followed to solve geometric problems. It involves using mathematical equations and concepts to find solutions to geometric questions.

2. How do you determine the optimal algorithm for a geometry problem?

The optimal algorithm for a geometry problem is determined by considering various factors such as the complexity of the problem, the available data, and the desired level of accuracy. It also involves testing different algorithms and evaluating their efficiency in solving the problem.

3. What are the common techniques used in developing an optimal algorithm for geometry problems?

Some common techniques used in developing an optimal algorithm for geometry problems include using geometric formulas, applying mathematical principles such as symmetry and congruence, and using computer programming and algorithms to solve complex problems.

4. How can an optimal algorithm for geometry problems be applied in real-life situations?

An optimal algorithm for geometry problems can be applied in various real-life situations such as in engineering, architecture, and design. It can also be used in navigation systems, computer graphics, and 3D modeling to solve complex geometric problems efficiently and accurately.

5. What are the benefits of using an optimal algorithm for geometry problems?

Using an optimal algorithm for geometry problems can lead to more accurate and efficient solutions, saving time and resources. It also allows for more complex problems to be solved and can be applied in a wide range of fields, making it a versatile problem-solving tool.

Suggested for: Algorithm which is optimal for these geometry problems

Replies
4
Views
979
Replies
5
Views
679
Replies
41
Views
2K
Replies
38
Views
3K
Replies
1
Views
177
Replies
1
Views
860
Replies
1
Views
713
Replies
1
Views
691
Replies
18
Views
1K
Back
Top