Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!pantor!richard
From: richard@pantor.UUCP (Richard Sargent)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of points
Message-ID: <38.UUL1.3#5109@pantor.UUCP>
Date: 7 Dec 89 14:20:55 GMT
References: <160@fornax.cs.sfu.ca>
Organization: Pansophic Systems Inc, Graphics Product Company
Lines: 27

This writer claimed a linear time solution is possible.

> From: shermer@cs.sfu.ca (Tom Shermer)
> Message-ID: <160@fornax.cs.sfu.ca>
> Date: 5 Dec 89 19:47:36 GMT

I agree. I may be wrong, but ... here is a sketch of how to do it.

Using a list of the points, take the first two, compute a circle
or sphere or hypersphere, etc. with the two points on the circle's
boundary. Take the next point. If the distance to the circle
center is less than the circle's radius, it is already inside and
can be discarded. Otherwise, calculate the point on the circle's
boundary opposite the new point. One way is intersect the line of
new point and center with the circle, and use the farthest intersect.
Using the new point and the calculated point, recompute a new circle,
as was done with the first two points.  Repeat as necessary.

I don't know how to prove that the result is the smallest enclosing
circle, but I expect if it isn't that it will be close enough for
all practical purposes.

I'd like to hear if this works / does the job.


Richard Sargent                   Internet: richard@pantor.UUCP
Systems Analyst                   UUCP:     uunet!pantor!richard