3 ms·
I had to refresh parts of that knowledge recently in connection with a very simple problem that has a complex algorithmic solution: given a finite set of points
by praptak 8y ago
I had to refresh parts of that knowledge recently in connection with a very simple problem that has a complex algorithmic solution: given a finite set of points on a 2D plane find the minimum radius disc that covers all points.
Even for the 3 points case the solution is not 100% trivial.
- onion2k 8y agoWhy isn't that a disc with a diameter equal to the distance between the two points that are farthest apart? Edit: Ah. I get it now. If the points made an equilateral triangle you'd want to put the disc on the triangle center. That sounds like a fun problem..
- praptak 8y agoYes, that's what I meant by the solution not being trivial even for 3 points. It's either the circumscribed circle (for acute triangles) or the longest edge being the diameter (for obtuse triangles). For a larger number of points it's generally the same, only you don't know which of the multiple possible triangles will work.