Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!purdue!decwrl!shelby!eos!jbm
From: jbm@eos.UUCP (Jeffrey Mulligan)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of points
Message-ID: <5678@eos.UUCP>
Date: 30 Nov 89 01:21:44 GMT
References:
Organization: NASA Ames Research Center, California
Lines: 35
rwang@caip.rutgers.edu (Ruye Wang) 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!
This problem was discussed at length some time ago. I think it was in this
newsgroup, but it may have been rec.puzzles or sci.math. There were
a bunch of incorrect or partially correct conjectures (I remember since
I was participating) which were ultimately followed by some definative
answers. I don't remember the details, but I think the 2-D solution
(which was discussed) should generalize to 3D just fine. What I remember
is something like: discard points not in covex hull, consider triples
(quadruples in 3D), if trangle (tetrahedron) is acute (analogous 3-D
property involving solid angle!?) find circumcircle (circumsphere), else use
side (face) opposite obtuse (whatever) angle as diameter (plane containing center & three pts). Search over all triples (quadruples), pick biggest radius.
Apologies in advance if this is another misguided guess.
But I believe a definitive answer (with scholarly references)
is in the news archives.
jeff
--
Jeff Mulligan (jbm@aurora.arc.nasa.gov)
NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035
(415) 694-3745