Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!asuvax!ncar!mephisto!rutgers!cmcl2!lanl!opus!afoiani From: afoiani@nmsu.EDU (Anthony Foiani) Newsgroups: comp.graphics Subject: Re: smallest sphere enclosing a set of points Message-ID: Date: 8 Dec 89 17:36:42 GMT References: <28@ <658@cditi.UUCP> <4893@skinner.nprdc.arpa> <679@dbrmelb.dbrhi.oz> <5497@nucleus.UUCP> Sender: news@nmsu.edu Organization: New Mexico State University, Las Cruces, NM Lines: 37 In-reply-to: mjb@nucleus.UUCP's message of 7 Dec 89 20:35:36 GMT In article <5497@nucleus.UUCP> mjb@nucleus.UUCP (Mark Bobak) writes: [...] ( Average(maxx,minx),Average(maxy,miny),Average(maxz,minz) ) Then, your radius would be longest of the distances from center point to any point. I tried a couple examples, let's use (-1,0),(1,0),(0,2) here: [...] Therefore, we have C(0,1) and radius Sqrt(2). [...] Good try, Mark; this is the quickest way to approximate this sphere, but it is NOT the smallest. [I thought it would work too, but managed to find the error before posting ;-)]. Notice that your proposed circle does indeed hit exactly on (-1,0) and (1,0); but it is ~0.4 units away from (0,2). The _smallest_ sphere enclosing three points is the sphere which hits those three points [non-colinearity assumed, of course]. In this example, it is... Courtesy of CRC Std Math, 28th Ed: R = radius of circumscribed triangle = a*b*c/(4*K) [where K is the area of the triangle] = sqrt(5)*sqrt(5)*2/[4*(2*2*0.5)] = 10/8 = 1.25 the points you picked make it easy for us to compute the center, which leaves us with Radius = 1.25 Center at (0,0.75) The method you mentioned is a good approximation. A slightly faster [but possibly much worse!] approximation is to find the bounding box for all the points, and let the radius equal the distance from the center to a corner. Bad accuracy but fairly quick, only one run through the distances. Tony -- tony foiani (afoiani@nmsu.edu) "And remember...don't lose your a.k.a. Tkil (mcsajf@nmsuvm1.bitnet) head..." -Ramirez, HIGHLANDER