Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!gistdev!dlp From: dlp@gistdev.gist.com (Dirk Pellett) Newsgroups: comp.graphics Subject: Re: smallest sphere enclosing a set of points Message-ID: <841@gistdev.gist.com> Date: 4 Dec 89 22:59:34 GMT References: <28@ <207400043@s.cs.uiuc.edu> <1989Dec3.190029.4916@utcs.utoronto.ca> Organization: Global Information Systems Technology Inc., Savoy, IL Lines: 24 Written 9:18 pm Nov 28, 1989 by rwang@caip.rutgers.edu: -> find the smallest sphere that encloses a set of given points, in both -> 2-D and 3-D (or even n-D, if you like). In article <207400043@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes: -> a simple minded solution which I think SHOULD work, but would be -> painstakingly slow and grows exponentially... should wouk for 2D or 3D -> take set of point and compute distances from every point to every other -> point. find the two points which are farthest away from one another. -> 1/2 the distance between them is the diameter of your enclosing -> circle/sphere. Center your circle/sphere on the halfway point of the -> line between them. disclaimer- This is simply an intuitve solution -> that came up. It may or may not have serious flaws. any comments? Yes. Try that method trying to enclose a simple equalateral triangle. One of the sides will become the diameter of the sphere, and the other point will be outside the sphere. Besides being god-awful slow, your intuitive method fails on the simplest test case. -- Dirk Pellett uunet!gistdev!dlp dlp@gistdev.gist.com If it isn't documented, it isn't implemented. -- Dirk Pellett uunet!gistdev!dlp dlp@gistdev.gist.com If it isn't documented, it isn't implemented. Brought to you by Super Global Mega Corp .com