Take the 2-minute tour ×

I am trying to find sphere that surly encompasses given list of points. Points will have x, y and z co-ordinate[Points are in 3D].

Actually I am trying to find new three points based on given list of points by some calculations like find MinX,MaxX ,MinY,MaxY,and MinZ and MaxZ and do some operation and find new three points

And I will draw sphere from these three points.

And I will also taking all these three points on the diameter of sphere so I have a unique sphere.

Is there any standard way for finding encompassing sphere of given list of points?

share|improve this question
So do you have three points or N points? And why do you take three points and put them onto diameter? –  maxim1000 Apr 21 '11 at 5:24
@ maxim1000,see i have update my question –  Pritesh Apr 21 '11 at 5:39
BTW, it takes 4 points to uniquely define a sphere. –  phkahler Apr 21 '11 at 13:30
3 Points are enough if we take three points on the diameter of sphere –  Pritesh Apr 21 '11 at 13:38
You can construct a circumsphere around a triangle by intersecting the perpendicular bisectors of 2 edges. However, I strongly encourage you to use Gärtners device instead - it's way more robust (and not much more code - check the Miniball_b thing in his sources) –  ltjax Apr 21 '11 at 14:28

2 Answers 2

Yes, the standard algorithm is Welzl's algorithm (assuming you want the minimal sphere around your points). Particularly the improved version of Gaertner is very useful, robust and numerically stable! It handles all the degenerate cases well too.

At its core, the algorithm permutes the points (randomly) to find the 1-4 points that lie on the boundary of the sphere. It's basically a clever trial-and-error algorithm. From these points, you can find the center by finding a point that has the same distance to all those points. Gärtner's version uses an improved numerical device to find the center. Also, it employs an extra pivoting step that presumably makes the algorithm work better for a large number of input points.

If all you want is a sphere around three points, I suggest you still use Gärtners "device" to compute the circumsphere of the triangle. Otherwise, the method will probably degenerate easily (i.e. when the triangle is very flat).

share|improve this answer
You may also want to take a look at github.com/hbf/miniball, which works especially well in high dimensions (up to 10,000, say). For 2D and 3D, Bernd Gärtner's implementation is probably fastest. For higher dimensions, the algorithm in the aforementioned Github project (by Bernd, Martin and me) will be much faster. For even higher dimensions, you may want to use "core-set" algorithms. –  Hbf Feb 20 '13 at 11:51

Do you need 3 points, or any number of points?

If you only need the answer for 3 points, each pair of points defines a line segment. Take the longest line segment. Take a sphere centered at the middle of that line segment, whose radius is half the length of the line segment. There are two cases.

  1. The third point is inside of that initial sphere. If so, then you have the smallest sphere.
  2. The third point is outside of that initial sphere. Then the solution at Find Circum Center of Three point of Triangle [Not using Compass] will give you the center of the smallest sphere containing those 3 points.

If you need an arbitrary number of points, I'd do some sort of iterative approximation algorithm. Since you don't seem like you need that, I won't work out the details.

share|improve this answer
i guess i was wrong –  Santosh Linkha Apr 21 '11 at 7:05

Your Answer


