Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!samsung!munnari.oz.au!bruce!dbrmelb!davidp From: davidp@dbrmelb.dbrhi.oz (David Paterson) Newsgroups: comp.graphics Subject: Re: smallest sphere enclosing a set of points Message-ID: <677@dbrmelb.dbrhi.oz> Date: 7 Dec 89 06:06:02 GMT References: <28@ <207400043@s.cs.uiuc.edu> <1989Dec3.190029.4916@utcs.utoronto.ca> Organization: CSIRO, Div. Building Constr. and Eng'ing, Melb., Australia Lines: 30 In article <1989Dec3.190029.4916@utcs.utoronto.ca>, sarathy@utcs.utoronto.ca (Rajiv Sarathy) writes: > > a) Calculate the mean distance of the points to the origin. O(n) > operation. > b) Place centre of point at this mean. (ie. assuming the mean is a > vector, place the centre at the tip of the vector, with the vector's > base at the origin). O(1) operation. > c) Calculate the maximum distance from this point to all other points. > O(n) operation. > d) Use this distance as the radius. > > Total: O(n) > > This might not yield the BEST solution (the smallest circle/sphere), > but it'll be pretty close. Actually, I'm not positive that > it won't work. I'll try it out after exams :-> > Doesn't work. Example in 2-D. Consider points (0,-1),(0,1),(1,0) Smallest circle has centre (0,0) and radius 1 but above method gives circle with centre (1/3,0) and radius sqrt(10/9). ------------------------------------------------------------------------ David Paterson, CSIRO, Highett, 3190, Victoria. 'I can't find my car keys' - Me 'But you don't have a car' - Wife 'Whew, I thought I was becoming forgetful'