The minimum circle will either touch 2 points that form a diameter, or will touch 3 points that form an acute or right triangle. Your algorithm can make a circle that touches only one point; thus it is not a solution.
See http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm for a discussion of algorithms, including a linear time algorithm. Dave On Oct 3, 1:53 am, eSKay <catchyouraak...@gmail.com> wrote: > I know this problem doesn't sound new, but it is new to me and I > thought I could get some of your insight into solving this. > > There are some ~1000 points on a plane. We need to find the minimum > radius circle that can hold all these points. > > a) What I thought is that, first of all we need to discard points that > do not have a say - "the inner points" - using any algorithm (i know a > vector implementation of the rubber stretching algorithm) to establish > points that affect the radius. > > Now we need some algorithm to decide the minimum radius. > > I have an idea, but I am not really sure: > > as step b, > we can find the average of the points coordinates, and then the radius > would be the distance to the farthest point. > But I cant really convince myself that this will always work. > > What do you say? > Am I on the right path? wrong path? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
