mcooper@s.cs.uiuc.edu (12/03/89)
/* 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). 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! /* 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? +-------------------------------------+----------------------------------------+ | "When the going gets weird, | | | the weird turn pro." | Marc Cooper mcooper@cs.uiuc.edu | | | University of Illinois, C-U | | -Hunter S. Thompson | | +-------------------------------------+----------------------------------------+
gkd@mentor.cc.purdue.edu (Keith Miyake) (12/03/89)
In article <207400043@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes: > >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. > This does not work, I thought of this as a possible solution also, but it is flawed. Consider the event of having a equilateral triangle -only 3 points. Then using this method, you will always exclude one point, since you take the midpoint of one of the edges. It seems that this can be accounted for and a circle/sphere can be found using this algorithm, but I haven't thought about the specifics of it. Keith miyake@cs.purdue.edu
pelegrin@geocub.greco-prog.fr (12/03/89)
>/* 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). > >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 >/* End of text from s.cs.uiuc.edu:comp.graphics */ This is a small algorithm, which has some weaknesses : Xmin = Ymin = Zmin = +infinite Xmax = Ymax = Zmax = -infinite /* Compute the bounding volume */ For each point in set { If Xpt < Xmin Xmin = Xpt If Ypt < Ymin Ymin = Ypt If Ypt < Ymin Ymin = Ypt If Xpt > Xmax Xmax = Xpt If Ypt > Ymax Ymax = Ypt If Zpt > Zmax Zmax = Zpt } /* Compute the APPROXIMATE center */ CX = Xmin + (Xmax - Xmin) / 2 CY = Ymin + (Ymax - Ymin) / 2 CZ = Zmin + (Zmax - Zmin) / 2 /* Now calculate the Minimum and Maximum diameters */ Dmin = +infinite Dmax = -infinite if (Xmax - Xmin > Dmax) Dmax = Xmax - Xmin if (Ymax - Ymin > Dmax) Dmax = Ymax - Ymin if (Zmax - Zmin > Dmax) Dmax = Zmax - Zmin if (Xmax - Xmin < Dmin) Dmin = Xmax - Xmin if (Ymax - Ymin < Dmin) Dmin = Ymax - Ymin if (Zmax - Zmin < Dmin) Dmin = Zmax - Zmin Dmin = Dmin * sqrt (3) Dmax = Dmax * sqrt (3) /* To follow, Compute by scattering of a better diameter */ /* You can first compute the distance of all points to */ /* the center of the sphereto optimize the process */ for i = 1 to XX { /* Choose it */ Dtmp = (Dmin + Dmax) /2 if (all points within the sphere of diameter Dtmp) Dmax = Dtmp else Dmin = Dtmp } Disclaimer : This is just an idea... f.p.
sarathy@utcs.utoronto.ca (Rajiv Sarathy) (12/04/89)
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 |
woody@rpp386.cactus.org (Woodrow Baker) (12/04/89)
I am curious, what possible use could the solution to this problem be?
josh@cditi.UUCP (Josh Muskovitz) (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).
->
-> 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!
- 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?
Oops. Your post has the same flaw mine did just before I killed it. Take the
case where there are three equidistant points. The solution is the the center
of the triangle these define, with the radius being the distance from there to
any of the three points. I couldn't resolve this.
--josh muskovitz
josh@uunet!cditimalloy@nprdc.arpa (Sean Malloy) (12/06/89)
In article <658@cditi.UUCP> josh@cditi.UUCP (Josh Muskovitz) writes: >In article <207400043@s.cs.uiuc.edu-, mcooper@s.cs.uiuc.edu writes: >-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? >Oops. Your post has the same flaw mine did just before I killed it. Take the >case where there are three equidistant points. The solution is the the center >of the triangle these define, with the radius being the distance from there to >any of the three points. I couldn't resolve this. 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. Sean Malloy | "The proton absorbs a photon Navy Personnel Research & Development Center | and emits two morons, a San Diego, CA 92152-6800 | lepton, a boson, and a malloy@nprdc.navy.mil | boson's mate. Why did I ever | take high-energy physics?"
meyer@unizh.UUCP (Urs Meyer) (12/07/89)
Check out the following references:
D. Jack Elzinga and Donald W. Hearn: The Minimum Covering Sphere Problem,
in Management Science, Vol 19(1), Sept 1972.
Jack Elzinga and Donald W. Hearn: Geometrical Solutions for Some
Minimax Location Problems, in Transportation Science Vol 6, 1972.
Nimrod Megiddo: Linear-Time Algorithms for Linear Programming in R3 and
Related Problems, in SIAM Journal of Computing, Vol 12(4), Nov 1983.
May be these refs should be included in Jef's weekly posting.
Urs Meyer
University of Zurich, Dept of Computer Science, Multi-Media Lab, CH-8057 Zurich
meyer@ifi.unizh.ch [ @relay.cs.net ], {uunet,...}!mcvax!cernvax!unizh!meyerdave@viper.Lynx.MN.Org (David Messer) (12/07/89)
In article <207400043@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes: > >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? Try it for three points in an equalateral (sp?) triangle... doesn't work. -- Remember Tiananmen Square. | David Messer dave@Lynx.MN.Org -or- | Lynx Data Systems ...!bungia!viper!dave
mcooper@s.cs.uiuc.edu (12/08/89)
ALLRIGHT already!!1 My solution fails! Jeeze!!! I goofed... And to malloy, who suggested a fix for it (averaging coords of all equidistant points...) It may work (or not. Don't have time to think this though) but it's still in exponential time... VERY slow.. Somwone mailed me a solution which apparently works in linear(!) time. Should I post it? +-------------------------------------+----------------------------------------+ | "When the going gets weird, | | | the weird turn pro." | Marc Cooper mcooper@cs.uiuc.edu | | | University of Illinois, C-U | | -Hunter S. Thompson | | +-------------------------------------+----------------------------------------+
lambert@cheops.eecs.unsw.oz (Timothy Lambert) (12/08/89)
/* Written 9:18 pm Nov 28, 1989 by rwang@caip.rutgers.edu in s.cs.uiuc.edu:comp.graphics */ 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 */ From article <207400043@s.cs.uiuc.edu>, by mcooper@s.cs.uiuc.edu: > 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. I'm afraid this doesn't work. Try the vertices of an equilateral triangle for a counter-example. See "Computational Geometry" by Preparata and Shamos for an answer to the 2D case. Tim
macphed@dvinci.usask.ca (Ian MacPhedran) (12/13/89)
From article <4893@skinner.nprdc.arpa>, by malloy@nprdc.arpa (Sean Malloy): > In article <658@cditi.UUCP> josh@cditi.UUCP (Josh Muskovitz) writes: >>In article <207400043@s.cs.uiuc.edu-, mcooper@s.cs.uiuc.edu writes: >>> [[Suggestion to use largest point to point distance as diameter of >>> minimum circle.]] >> [[Point of exception for equilateral triangle.]] > 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. You'll have to be more general than this, all isosceles triangles with equal angles between 45 and 60 degrees will fail, as will several more general triangles (those with the sum of the two smaller angles greater than 90 degrees). The case of the equilateral triangle is just a convenient one. Ian. Ian MacPhedran, Engineering Computer Centre, University of Saskatchewan. 2B13 Engineering Building, U. of S. Campus, Saskatoon, Sask., CANADA S7N 0W0 macphed@dvinci.USask.CA macphedran@sask.USask.CA macphedran@sask.BITNET -- Ian MacPhedran, Engineering Computer Centre, University of Saskatchewan. 2B13 Engineering Building, U. of S. Campus, Saskatoon, Sask., CANADA S7N 0W0 macphed@dvinci.USask.CA macphedran@sask.USask.CA macphedran@sask.BITNET