Path: utzoo!attcan!uunet!cs.utexas.edu!sun-barr!rutgers!att!alberta!uqv-mts!ualtavm.bitnet!ECULHAM
From: ECULHAM@UALTAVM.BITNET (Earl Culham)
Newsgroups: comp.graphics
Subject: Re: Ray Traced Bounding Spheres
Message-ID: <482@UALTAVM.BITNET>
Date: 15 May 89 23:07:45 GMT
References: <17241@versatc.UUCP> <17249@versatc.UUCP> <8411@phoenix.Princeton.EDU> <SARREL.89May14223947@galley.cis.ohio-state.edu>
Reply-To: ECULHAM@UALTAVM.BITNET
Organization: University of Alberta VM/CMS
Lines: 37
Disclaimer: Author bears full responsibility for contents of this article

>Here is my solution, which I _know_ to be linear in the number of
>points.
>
>Problem:
>Given a set of points in three space, find the two that are farthest
>apart and use them to define a minimum bounding sphere.
>
>Solution:
>1) Pick a point, any point, call it p1
>2) Find the farthest point from p1, call it p2.
>3) Find the farthest point from p2, call it p3.
>4) Use p2, p3 and the distance between them to define your minimum
>   bounding sphere.
>
>That's it.  It is guaranteed to be linear, too.
>
 
This algorithm does not necessarily find the two points furthest apart.
 
Even if it did, the two points furthest apart do not need to be on
opposite sides of the minimum bounding sphere.
 
Counter Example (in only 2D)
A = (0,0)
B = (0,10)
C = (6,5)
D = (-6,5)
 
Choose P1 to be A.
P2 becomes B.
P3 becomes A.
 
This did not find the two furthest points C and D.
 
If we forget about the point D, then this algorithm does find the two
furthest. But the circle delimited by these two furthest points, does
not contiain the point C.