Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!gistdev!dlp
From: dlp@gistdev.gist.com (Dirk Pellett)
Newsgroups: comp.graphics
Subject: Re: smallest sphere enclosing a set of points
Message-ID: <841@gistdev.gist.com>
Date: 4 Dec 89 22:59:34 GMT
References: <28@ <207400043@s.cs.uiuc.edu> <1989Dec3.190029.4916@utcs.utoronto.ca>
Organization: Global Information Systems Technology Inc., Savoy, IL
Lines: 24
Written 9:18 pm Nov 28, 1989 by rwang@caip.rutgers.edu:
-> 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).
In article <207400043@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes:
-> 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?
Yes. Try that method trying to enclose a simple equalateral triangle.
One of the sides will become the diameter of the sphere, and the other
point will be outside the sphere. Besides being god-awful slow, your
intuitive method fails on the simplest test case.
--
Dirk Pellett uunet!gistdev!dlp dlp@gistdev.gist.com
If it isn't documented, it isn't implemented.
--
Dirk Pellett uunet!gistdev!dlp dlp@gistdev.gist.com
If it isn't documented, it isn't implemented.