Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!clyde!uunet!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!ucla-cs!uci-ics!orion.oac.uci.edu!ucsd!nprdc!malloy
From: malloy@nprdc.arpa (Sean Malloy)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of
Message-ID: <4893@skinner.nprdc.arpa>
Date: 5 Dec 89 16:37:10 GMT
References: <28@<Nov- <207400043@s.cs.uiuc.edu> <658@cditi.UUCP>
Reply-To: malloy@nprdc.arpa (Sean Malloy)
Organization: Navy Personnel R&D Center, San Diego
Lines: 31

In article <658@cditi.UUCP> josh@cditi.UUCP (Josh Muskovitz) writes:
>In article <207400043@s.cs.uiuc.edu-, mcooper@s.cs.uiuc.edu writes:
>-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.

Then generalize it. Find the largest distance between any two points.
Take all the pairs of points with that separation, and average their
coordinates. This will give you the center of the sphere; the distance
from that point to any of the equidistant points will give you the
radius.

Each point in the set of points with largest separation gets counted
twice in the averaging, but since you divide by the number of endpoints,
not the number of separations, the averaging still works.


 Sean Malloy					| "The proton absorbs a photon
 Navy Personnel Research & Development Center	| and emits two morons, a
 San Diego, CA 92152-6800			| lepton, a boson, and a
 malloy@nprdc.navy.mil				| boson's mate. Why did I ever
						| take high-energy physics?"