Newsgroups: comp.graphics
Path: utzoo!utgpu!sarathy
From: sarathy@utcs.utoronto.ca (Rajiv Sarathy)
Subject: Re: smallest sphere enclosing a set of
Message-ID: <1989Dec3.190029.4916@utcs.utoronto.ca>
Organization: University of Toronto Computing Services
References: <28@<Nov> <207400043@s.cs.uiuc.edu>
Date: Sun, 3 Dec 89 19:00:29 GMT

In article <207400043@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes:
>
>/* Written  9:18 pm  Nov 28, 1989 by rwang@caip.rutgers.edu in s.cs.uiuc.edu:comp.graphics */
>/* ---------- "smallest sphere enclosing a set of" ---------- */
>
>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).
>...
>/* End of text from s.cs.uiuc.edu:comp.graphics */
>
>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?

    1.	If you keep a 2-d
	matrix of distances, then when adding the i-th point, you have
	to calculate i-1 distances.  Is this exponential? ;-)
	(You don't need to fill every element of the matrix.  You just need
	the triangular portion either above or below the diagonal -- this
	will be square matrix)

    2.	Placing the centre of the sphere/circle on the centre of the line
	connecting the two farthest points won't work at all if these two
	points happen to be far away from the remaining points.

    A better solution, though still not as good as the one posted several
    days ago is to do the following:

	a) Calculate the mean distance of the points to the origin. O(n)
	   operation.
	b) Place centre of point at this mean. (ie. assuming the mean is a
	   vector, place the centre at the tip of the vector, with the vector's
	   base at the origin). O(1) operation.
	c) Calculate the maximum distance from this point to all other points.
	   O(n) operation.
	d) Use this distance as the radius.

	Total: O(n)

	This might not yield the BEST solution (the smallest circle/sphere),
	but it'll be pretty close.  Actually, I'm not positive that
	it won't work.  I'll try it out after exams :->

-- 
 _____________________________________________________________________________
| Disclaimer:  I'm just an undergrad. All views and opinions are therefore  _ |
| 	       my own.   /\    /\    /-----------------------------------oO(_)|
|                       /  \  /  \  /     NetNorth: sarathy@utorgpu           |


Brought to you by Super Global Mega Corp .com