Path: utzoo!attcan!uunet!wuarchive!uwm.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!s.cs.uiuc.edu!mcooper
From: mcooper@s.cs.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of
Message-ID: <207400043@s.cs.uiuc.edu>
Date: 2 Dec 89 17:38:25 GMT
References: <28@<Nov>
Lines: 36
Nf-ID: #R:<Nov:28:s.cs.uiuc.edu:207400043:000:1519
Nf-From: s.cs.uiuc.edu!mcooper    Dec  1 09:16:00 1989


/* Written  9:18 pm  Nov 28, 1989 by rwang@caip.rutgers.edu in s.cs.uiuc.edu:comp.graphics */
/* ---------- "smallest sphere enclosing a set of" ---------- */

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!
/* End of text from s.cs.uiuc.edu:comp.graphics */


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?



+-------------------------------------+----------------------------------------+
|  "When the going gets weird,        |                                        |
|              the weird turn pro."   |  Marc Cooper	mcooper@cs.uiuc.edu    |
|		  		      |  University of Illinois, C-U	       |
|		 -Hunter S. Thompson  |					       |
+-------------------------------------+----------------------------------------+


Brought to you by Super Global Mega Corp .com