rwang@caip.rutgers.edu (Ruye Wang) (11/29/89)
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!
jbm@eos.UUCP (Jeffrey Mulligan) (11/30/89)
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
wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) (12/01/89)
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). The smallest enclosing circle is a well known problem. It can be solved with a farthest point Voronoi diagram, see Preparata & Shamos. In 2-D the time is NlgN. In 3-D, I don't know the time, but it might be N^2 since the closest point VorD is that complex. (The farthest point VorD might be simpler.) -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180
davidp@dbrmelb.dbrhi.oz (David Paterson) (12/04/89)
In article <Nov.28.22.18.43.1989.8200@caip.rutgers.edu>, 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! Here are two solution methods. A slow one that works in n-D and a fast one that works in 2-D and possibly 3-D. FIRST METHOD (Very slow) For all sets of n+1 points Find the smallest n-sphere containing these n+1 points End for Find the largest of these n-spheres Stop The smallest n-sphere containing n+1 points is found iteratively (from the smallest n-1 sphere containing n points) as follows: For all sets of n points Find the smallest (n-1)-sphere containing these points End for Find the largest of these (n-1)-spheres Consider an n-sphere with the same centre and radius If the excluded point lies within this n-sphere then The required n-sphere is this n-sphere Else The required n-sphere is the n-sphere touching all n+1 points End if Return The smallest 1-sphere containing 2 points (call these P1 and P2) has centre (P1+P2)/2 and radius |P1-P2|/2. To find an n-sphere touching n+1 points requires the simultaneous solution of n+1 quadratic equations. This can be solved by Newton's method. SECOND METHOD (very fast) EXAMPLE IN 2-DIMENSIONS **1-D Part** For all sets of 2 points (call these P1,P2) Find the smallest circle containing these two points End for Find the largest of these circles **2-D Part** For all points outside this circle (call this P3) If no such points Stop Find the circle touching P1,P2 & P3 End for Find the largest of these circles 10 For all points outside this circle (call this P4) If no such points Stop Find the smallest circle containing P3 & P4 Find which of P1,P2 is outside this circle (call this P5) Find the circle touching P3,P4 & P5 End for Find the largest of these circles Set P1 <-- P5; P2 <-- P3; P3 <-- P4 Go to 10 EXAMPLE IN 3-DIMENSIONS **1-D Part** For all sets of two points (call these P1,P2) Find the smallest sphere containing these two points End for Find the largest of these spheres **2-D Part** For all points outside this sphere (call this P3) If no such points Stop Find the smallest sphere containing P1,P2 & P3 End for Find the largest of these spheres **3-D Part** For all points outside this sphere (call this P4) If no such points Stop Find the sphere touching P1,P2,P3 & P4 End for Find the largest of these spheres 10 For all points outside this sphere (call this P5) If no such points Stop Find which of P1,P2,P3 is furthest from P5 (call this P6) Find the smallest sphere containing P4,P5 & P6 Find which of P1,P2,P3 is outside this sphere (call this P7) Find the sphere touching P4,P5,P6 & P7 End for Find the largest of these spheres Set P1 <-- P6; P2 <-- P7; P3 <-- P4; P4 <-- P5 Go to 10 Note: I know that the 2-D example above always gives the correct answer but I can't be 100% sure that the 3-D example does. ------------------------------------------------------------------- David Paterson CSIRO B,C&E Highett Victoria 3190 There are many people out there who have more money than sense. Few of them are rich. ------------------------------------------------------------------
davidp@dbrmelb.dbrhi.oz (David Paterson) (12/05/89)
In article <207400043@s.cs.uiuc.edu>, mcooper@s.cs.uiuc.edu 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). > > 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. Fails miserably, I used it as a first approximation in the 'fast solution' method posted to this newsgroup two days ago. --------------------------------------------------------------------------- David Paterson CSIRO, Highett, 3190, Victoria 'I can't find my car keys' 'You don't have a car' 'Whew, that's a relief, I thought I was becoming forgetful'
dlp@gistdev.gist.com (Dirk Pellett) (12/05/89)
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.shermer@cs.sfu.ca (Tom Shermer) (12/06/89)
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). > This problem can be solved in linear time (in any fixed dimension) by the technique of prune-and-search (sometimes called ``Megiddo's Technique''), either directly or by first converting the problem to a linear program. The most relevant reference (for 2d & 3d) is: Linear-time Algorithms for Linear Programming in R^3 and Related Problems, Nimrod Megiddo, SIAM J. Comput, v. 12, No. 4, Nov 1983, pp. 759-776. Other related references: Linear time algorithms for two- and three- variable linear programs, M.E. Dyer, SIAM J. Comput, v. 13, 1984, 31-45. On a multidimensional search technique and its application to the Euclidean one-center problem, M. E. Dyer, Dept. Math and Stats TR, Teesside Polytechnic, Middlesbrough, Cleveland TS1 3BA, UK, 1984. Linear programming in linear time when the dimension is fixed, N. Megiddo, JACM 31, 1984, 114-127 The weighted Euclidean 1-center problem, N. Megiddo, Mathematics of Operations Research 8, 1983, 498-504 On the Ball Spanned by Balls N. Megiddo, manuscript (this may have appeared in the literature by now) Tom Shermer School of Computing Science Simon Fraser University Burnaby, BC, Canada V5A 1S6 (604) 291-3601 shermer@cs.sfu.ca
davidp@dbrmelb.dbrhi.oz (David Paterson) (12/07/89)
In article <1989Dec3.190029.4916@utcs.utoronto.ca>, sarathy@utcs.utoronto.ca (Rajiv Sarathy) writes: > > 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 :-> > Doesn't work. Example in 2-D. Consider points (0,-1),(0,1),(1,0) Smallest circle has centre (0,0) and radius 1 but above method gives circle with centre (1/3,0) and radius sqrt(10/9). ------------------------------------------------------------------------ David Paterson, CSIRO, Highett, 3190, Victoria. 'I can't find my car keys' - Me 'But you don't have a car' - Wife 'Whew, I thought I was becoming forgetful'
davidp@dbrmelb.dbrhi.oz (David Paterson) (12/07/89)
In article <4893@skinner.nprdc.arpa>, malloy@nprdc.arpa (Sean Malloy) writes: > > Then generalize it. Find the largest distance between any two points. > Take all the pairs of points with that separation, and average their > coordinates. This will give you the center of the sphere; the distance > from that point to any of the equidistant points will give you the > radius. > > Each point in the set of points with largest separation gets counted > twice in the averaging, but since you divide by the number of endpoints, > not the number of separations, the averaging still works. > Sorry, still doesn't work, consider, for instance the circle surrounding points (-1,0),(1,0),(0,2). My solution was (see earlier posting) to solve simultaneously three quadratic equations using Newton's method. Does anyone know a quicker way? ----------------------------------------------------------------------- David Paterson, CSIRO, Highett, 3190, Victoria, Australia
richard@pantor.UUCP (Richard Sargent) (12/07/89)
This writer claimed a linear time solution is possible. > From: shermer@cs.sfu.ca (Tom Shermer) > Message-ID: <160@fornax.cs.sfu.ca> > Date: 5 Dec 89 19:47:36 GMT I agree. I may be wrong, but ... here is a sketch of how to do it. Using a list of the points, take the first two, compute a circle or sphere or hypersphere, etc. with the two points on the circle's boundary. Take the next point. If the distance to the circle center is less than the circle's radius, it is already inside and can be discarded. Otherwise, calculate the point on the circle's boundary opposite the new point. One way is intersect the line of new point and center with the circle, and use the farthest intersect. Using the new point and the calculated point, recompute a new circle, as was done with the first two points. Repeat as necessary. I don't know how to prove that the result is the smallest enclosing circle, but I expect if it isn't that it will be close enough for all practical purposes. I'd like to hear if this works / does the job. Richard Sargent Internet: richard@pantor.UUCP Systems Analyst UUCP: uunet!pantor!richard
mjb@nucleus.UUCP (Mark Bobak) (12/08/89)
In article <679@dbrmelb.dbrhi.oz> davidp@dbrmelb.dbrhi.oz (David Paterson) writes: > > >In article <4893@skinner.nprdc.arpa>, malloy@nprdc.arpa (Sean Malloy) writes: >> >> Then generalize it. Find the largest distance between any two points. >> Take all the pairs of points with that separation, and average their >> coordinates. This will give you the center of the sphere; the distance >> from that point to any of the equidistant points will give you the >> radius. >> >> Each point in the set of points with largest separation gets counted >> twice in the averaging, but since you divide by the number of endpoints, >> not the number of separations, the averaging still works. >> >Sorry, still doesn't work, consider, for instance the circle surrounding >points (-1,0),(1,0),(0,2). > >My solution was (see earlier posting) to solve simultaneously three >quadratic equations using Newton's method. Does anyone know a quicker >way? >----------------------------------------------------------------------- >David Paterson, CSIRO, Highett, 3190, Victoria, Australia Hmm....Could everyone be overlooking the obvious? It seems to me, for a circle, sphere, hypersphere, (in 2D,3D,4D, or N-D for that matter) that will enclose a set of points, simply find the max x,y,z and min x,y,z. Then, the center point should be: ( Average(maxx,minx),Average(maxy,miny),Average(maxz,minz) ) Then, your radius would be longest of the distances from center point to any point. I tried a couple examples, let's use (-1,0),(1,0),(0,2) here: Max X = 1, Min X = -1, Max Y = 2, Min Y = 0, Then, Average X = (1+(-1))/2 = 0 and Average Y = (2+0)/2 = 1 So, Center Point = (0,1) Distance from (0,1) to (-1,0) is: Sqrt((0 - (-1))^2 + (1 - 0)^2) = Sqrt(1+1) = Sqrt(2) = 1.414 Distance from (0,1) to (1,0) is: Sqrt( (0 - (-1))^2 + (1 - 0)^2 ) = Sqrt(1+1) = Sqrt(2) = 1.414 Distance from (0,1) to (0,2) is: Sqrt( (0 - 0)^2 + (1 - 2)^2 ) = Sqrt(0+1) = 1 Therefore, we have C(0,1) and radius Sqrt(2). This solution should work for N-Dimensional space. -- Mark Bobak The Nucleus Public Access Unix, Clarkston, Mi. mjb@nucleus.mi.org mjb@m-net.ann-arbor.mi.us
mjb@nucleus.UUCP (Mark Bobak) (12/08/89)
In article <5497@nucleus.UUCP> mjb@nucleus.UUCP (Mark Bobak) writes: > >Distance from (0,1) to (1,0) is: >Sqrt( (0 - (-1))^2 + (1 - 0)^2 ) = Sqrt(1+1) = Sqrt(2) = 1.414 > Sorry, that should read: Distance from (0,1) to (1,0) is: Sqrt( (0 - 1)^2 + (1 - 0)^2 ) = Sqrt(1+1) = Sqrt(2) = 1.414 It didn't make a difference here, but I thought I'd better fix that before I had 18 different follow-ups pointing it out....:-) -- Mark Bobak The Nucleus Public Access Unix, Clarkston, Mi. mjb@nucleus.mi.org mjb@m-net.ann-arbor.mi.us
afoiani@nmsu.EDU (Anthony Foiani) (12/09/89)
In article <5497@nucleus.UUCP> mjb@nucleus.UUCP (Mark Bobak) writes:
[...]
( Average(maxx,minx),Average(maxy,miny),Average(maxz,minz) )
Then, your radius would be longest of the distances from center point to any
point. I tried a couple examples, let's use (-1,0),(1,0),(0,2) here:
[...]
Therefore, we have C(0,1) and radius Sqrt(2).
[...]
Good try, Mark; this is the quickest way to approximate this sphere,
but it is NOT the smallest. [I thought it would work too, but managed
to find the error before posting ;-)].
Notice that your proposed circle does indeed hit exactly on (-1,0) and
(1,0); but it is ~0.4 units away from (0,2). The _smallest_ sphere
enclosing three points is the sphere which hits those three points
[non-colinearity assumed, of course]. In this example, it is...
Courtesy of CRC Std Math, 28th Ed:
R = radius of circumscribed triangle = a*b*c/(4*K)
[where K is the area of the triangle]
= sqrt(5)*sqrt(5)*2/[4*(2*2*0.5)] = 10/8 = 1.25
the points you picked make it easy for us to compute the center, which
leaves us with
Radius = 1.25 Center at (0,0.75)
The method you mentioned is a good approximation. A slightly faster
[but possibly much worse!] approximation is to find the bounding box
for all the points, and let the radius equal the distance from the
center to a corner. Bad accuracy but fairly quick, only one run
through the distances.
Tony
--
tony foiani (afoiani@nmsu.edu) "And remember...don't lose your
a.k.a. Tkil (mcsajf@nmsuvm1.bitnet) head..." -Ramirez, HIGHLANDERjosh@cditi.UUCP (Josh Muskovitz) (12/09/89)
In article <679@dbrmelb.dbrhi.oz>, davidp@dbrmelb.dbrhi.oz (David Paterson) writes: > In article <4893@skinner.nprdc.arpa>, malloy@nprdc.arpa (Sean Malloy) writes: > > Then generalize it. Find the largest distance between any two points. text deleted > Sorry, still doesn't work, consider, for instance the circle surrounding > points (-1,0),(1,0),(0,2). > ----------------------------------------------------------------------- > David Paterson, CSIRO, Highett, 3190, Victoria, Australia It's not fair to dismiss this case using negative points. To avoid this, simply transform the points into the first octant, try again, and transform the sphere back. Or is that too simple? Josh Muskovitz Computer Design, Inc. josh@uunet!cditi
lambert@cheops.eecs.unsw.oz (Timothy Lambert) (12/11/89)
From article <5497@nucleus.UUCP>, by mjb@nucleus.UUCP (Mark Bobak): > Hmm....Could everyone be overlooking the obvious? It seems to me, for a > circle, sphere, hypersphere, (in 2D,3D,4D, or N-D for that matter) that will > enclose a set of points, simply find the max x,y,z and min x,y,z. Then, the > center point should be: > ( Average(maxx,minx),Average(maxy,miny),Average(maxz,minz) ) > Then, your radius would be longest of the distances from center point to any > point. I tried a couple examples, let's use (-1,0),(1,0),(0,2) here: [Calculation deleted] > Therefore, we have C(0,1) and radius Sqrt(2). This encloses the points but we want the _smallest_ circle. For three points this is just the circumcircle which has centre (0,0.75) and radius 1.25. (You can find the equation for the circumcircle in the CRC tables.) Tim
dave@viper.Lynx.MN.Org (David Messer) (12/13/89)
If the center of the sphere is the vector C then its radius
is: r = maximum_for_all_i( |X(i) - C| ) where |X(i) - C| is
the distance from the center to point i. So all you need to
do is solve dr/dC = 0 to find C.
I leave the calculation of dr/dC as an exercise for the
student.
I hope this clarifies things. ;->
--
Remember Tiananmen Square. | David Messer dave@Lynx.MN.Org -or-
| Lynx Data Systems ...!bungia!viper!davedavidp@dbrmelb.dbrhi.oz (David Paterson) (12/15/89)
We've had lots of solutions to this problem posted. I've posted two already
(see above reference). The person who asked is probably sick to death of
them now. I'll test his patience a little bit more by posting this 'fun'
solution.
First a comment on the two solutions that I posted earlier. The first
(brute force) method has convergence order m^(n+1). It can be speeded up
considerably by first finding the convex hull. The second (bottom up)
method has convergence m^2 at best. It can be made watertight in n
dimensions by inserting a bit of the brute force method when it is
needed to find the smallest n-sphere containing n+2 points when this is
required.
The 'fun' solution below is watertight in n dimensions and has convergence
order m. It's not the fastest algorithm of order m but it sure is the
shortest. Here it is:
PARAMETER(MAXDIMENS=100,MAXPOINTS=100000)
DIMENSION POINTS(MAXDIMENS,MAXPOINTS),P0(MAXDIMENS),P1(MAXDIMENS)
READ *, IDIMENSION,IPOINTS,NSTEPS
READ *, ((POINTS(I,J),I=1,IDIMENSION),J=1,IPOINTS)
DO 10 I=1,IDIMENSION
10 P0(I)=0.
DISTMAX=0.
DO 30 J=1,IPOINTS
DISTANCE=0.
DO 20 I=1,IDIMENSION
20 DISTANCE=DISTANCE+(P0(I)-POINTS(I,J))**2
30 IF(DISTANCE.GT.DISTMAX) DISTMAX=DISTANCE
DO 80 N=1,NSTEPS
DO 40 I=1,IDIMENSION
40 P1(I)=P0(I)+RAND()-.5
XLENMAX=0.
DO 60 J=1,IPOINTS
XLENGTH=0.
DO 50 I=1,IDIMENSION
50 XLENGTH=XLENGTH+(P1(I)-POINTS(I,J))**2
60 IF(XLENGTH.GT.XLENMAX) XLENMAX=XLENGTH
IF(XLENMAX.LT.DISTMAX) THEN
DISTMAX=XLENMAX
DO 70 I=1,IDIMENSION
70 P0(I)=P1(I)
END IF
80 CONTINUE
PRINT *,'RADIUS=',SQRT(DISTMAX)
PRINT *,'CENTRE=',(P0(I),I=1,IDIMENSION)
STOP
END
Here P0 approaches the centre of the n-sphere as N tends to infinity.
NSTEP controls the speed and accuracy of the solution. RAND() denotes
a function that returns a different random number between 0 and 1 each
time it is called. If you don't already have such a function try the
following:
FUNCTION RAND()
PARAMETER(K=5701,J=3612,M=566927)
RM=M
IRAND=MOD(J*INT(RAND*RM)+K,M)
RAND=(IRAND+.5)/RM
RETURN
END
The algorithm, although it is of order m, is woefully inefficient. The
'fun' part consists of playing around with ways to speed it up. For
example, we could replace:
10 P0(I)=0.
by
10 P0(I)=POINT(I,1)
or set P0(I) to be the mean of all points or something else. We could
replace:
40 P1(I)=P0(I)+RAND()-.5
by
40 P1(I)=P0(I)+(RAND()-.5)*.1*SQRT(DISTMAX)
or
40 P1(I)=P0(I)+(RAND()-.5)*SQRT(DISTMAX)/LOG(N+5.)
or move a random distance in a direction towards the point furthest
from P0(I) or something else. We could replace:
DO 80 N=1,NSTEPS
by a better convergence criterion. The possibilities for playing around
with this method are literally endless.
------------------------------------------------------------------------
David Paterson, CSIRO Division of Building, Construction and Engineering,
Highett, Victoria, AUSTRALIA 3190.
------------------------------------------------------------------------poirier@dg-rtp.dg.com (Charles Poirier) (12/22/89)
In article <AFOIANI.89Dec8103642@dante.nmsu.EDU> afoiani@nmsu.EDU (Anthony Foiani) writes: >The _smallest_ sphere enclosing three points is the sphere which hits >those three points [non-colinearity assumed, of course]. This is only true if the triangle has no angle > 90 degreees. Cheers, Charles Poirier