Re: Smallest enclosing circle

*To*: mathgroup at smc.vnet.net*Subject*: [mg50130] Re: Smallest enclosing circle*From*: "Dr. Wolfgang Hintze" <weh at snafu.de>*Date*: Mon, 16 Aug 2004 06:45:40 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Over the weekend I had no contact to the internet - but had a nice time trying to solve this marvellous problem - which I couldn't. I'm nevertheless posting what I did without first reading all other messages. Hence you can judge beforehand if it is worth reading further... Here are my (preliminary) results: 1) Using ConvexHull of the package DiscreteMath`ComputationalGeometry` the problem can be traced back to finding the smallest enclosing circle (SEC) for a convex (irregular) polygon. This (at least) can reduce the number of points to be considered. BTW: this packages seems to have no solution to our problem. 2) Scaling to lower limit Let A and B be two points which have the maximum possible distance dMax of all pairs of points. We draw a circle through A and B with diameter equal to the distance between A and B. This circle is called the minimum circle. We normalize the problem so that the minimum circle has radis unity. It is obvious then that the any enclosing circle must have at least radius unity. 3) "Worst" arragement of points What is the "worst" arrangement of points? This is by definition an arragement which requires the greatest SEC. A related question ist: what is the radius rMax of the SEC of the worst arragement as measured in units of dMax? My preliminary results show that a lower limit for rMax is equal to 2/Sqrt(3) = 1.1547... This is the case when three points form an equilateral triangle, the points A and B (as above) and a point E having distance unity from A and from B. 4) Picture of the situation (might be of interest to others as well) This can be generated using the following command lines: In[15]:= Off[General::spell]; In[1]:= p2g[x_] := Graphics[Point[x]]; In[22]:= pA = {-1, 0}; gpA = p2g[pA]; gTextA = Graphics[Text["A", pA - {0.1, 0}]]; In[23]:= pB = {1, 0}; gpB = p2g[pB]; gTextB = Graphics[Text["B", pB + {0.1, 0}]]; In[24]:= pM = (pA + pB)/2; gpM = p2g[pM]; gTextM = Graphics[Text["M", pM - {0, 0.15}]]; In[25]:= pC = {-0.3, 0.6}; gpC = p2g[pC]; gTextC = Graphics[Text["C", pC - {0.1, 0}]]; In[26]:= pD = {0.2, -0.6}; gpD = p2g[pD]; gTextD = Graphics[Text["D", pD - {0.1, 0}]]; In[27]:= pE = {0, Sqrt[3]}; gpE = p2g[pE]; gTextE = Graphics[Text["E", pE + {0, 0.15}]]; In[28]:= pF = {0, -Sqrt[3]}; gpF = p2g[pF]; gTextF = Graphics[Text["F", pF - {0, 0.15}]]; In[29]:= pG = {-0.1, 1.3}; gpG = p2g[pG]; gTextG = Graphics[Text["G", pG - {0.1, 0}]]; In[30]:= pH = {-0.2, -1.4}; gpH = p2g[pH]; gTextH = Graphics[Text["H", pH - {0.1, 0}]]; In[31]:= pR = {Sqrt[3] - 1, 1}; gpR = p2g[pR]; gTextR = Graphics[Text["R", pR + {0.1, 0}]]; In[32]:= pS = {Sqrt[3] - 1, -1}; gpS = p2g[pS]; gTextS = Graphics[Text["S", pS + {0.1, 0}]]; In[33]:= gLAB = Graphics[Line[{pA, pB}]]; In[34]:= picMinCircle = Graphics[Circle[pM, 1]]; In[35]:= eps = 0.3; In[36]:= gBogenUmA = Graphics[Circle[pA, 2, {-\[Pi]/2 + eps, \[Pi]/2 - eps}]]; gBogenUmB = Graphics[Circle[pB, 2, {-3\[Pi]/2 + eps, -\[Pi]/2 - eps}]]; In[38]:= ps = 0.03; Show[Graphics[PointSize[ps]], gpA, gpB, gpM, gLAB, gpC, gpD, gpE, gpF, gpG, gpH, gpR, gpS, gTextA, gTextB, gTextM, gTextC, gTextD, gTextE, gTextF, gTextG, gTextH, gTextR, gTextS, picMinCircle, gBogenUmA, gBogenUmB, AspectRatio -> Automatic, PlotRange -> All]; Regards, Wolfgang Steve Gray wrote: > Given n points in the plane, I want to find the smallest > enclosing circle. Does anyone have Mathematica code to do this? > I will be grateful for any tips. > > Steve Gray > >