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 Brought to you by Super Global Mega Corp .com