Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!cditi!josh
From: josh@cditi.UUCP (Josh Muskovitz)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of
Message-ID: <658@cditi.UUCP>
Date: 5 Dec 89 14:07:35 GMT
References: <28@<Nov- <207400043@s.cs.uiuc.edu>
Organization: CDI Technologies Inc., Grand Rapids, MI
Lines: 27

In article <207400043@s.cs.uiuc.edu-, mcooper@s.cs.uiuc.edu writes:

-> I need the solution for the following problem:
-> 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).
-> 
-> I though it was a easy problem. But then I realized that it was not
-> that easy, at least to me.
-> 
-> If anyone knows the answer, would you please email it to me? Thank you
-> very much!

- 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?

Oops.  Your post has the same flaw mine did just before I killed it.  Take the
case where there are three equidistant points.  The solution is the the center
of the triangle these define, with the radius being the distance from there to
any of the three points.  I couldn't resolve this.

--josh muskovitz
josh@uunet!cditi