# Sphere that goes through 4 vertices of tetrahedron

## Recommended Posts

dali    195
Hello! I need a stable and fast way of creating a sphere that goes through the 4 vertices of a tetrahedron. I solved it in a hackish way but sometimes the algortihm creates bad result... How would you solve this problem? Thanks a lot!!!

##### Share on other sites
This isn't possible in general. Is there some constraint on your tetrahedron you're not telling us about?

For example, (0, 0, 0), (1, 1, 0), (2, 1, 0), (767, 1, 1) will have no such sphere. Not by a long shot.

Edit: That's not actually true. It is for (0, 0, 0), (1, 1, 0), (2, 1, 0), (767, 1, 0), though.

Regards

[Edited by - TheAdmiral on November 26, 2006 7:25:09 PM]

##### Share on other sites
dali    195
Yeah thats true. I need this for making a 3d delaunay triangulation to find out if one point is inside the sphere of the tet. The solution should be very fast and should make nearly correct results.

##### Share on other sites
Zipster    2359
It's possible to find a sphere that contains all four points, but as TheAdmiral aluded to your original problem is super-constrained, meaning that in general there won't be a solution. However that doesn't mean you won't get lucky and be handed a set of four points that are all on the surface of a sphere, which is what makes a solution possible in rare cases.

Off the top of my head, what you could do is take all combinations of 3 points and build a sphere from each of them. Then choose the smallest sphere that contains all the points. The reason this if off the top of my head is because I haven't considered the possibility of none of the spheres meeting the criteria or what to do when (if?) this case does occur.

##### Share on other sites
On second thoughts, the system is actually overdetermined only on a 1-dimensional subspace.

As alvaro's link establishes, we need any triplet of points to be non-collinear and all four to be non-planar. Given this, however, a sphere necessarily does exist, by rank-nullity. Who'd have guessed? [rolleyes].

We can picture it this way:
Pick any three points. We can create a unique circle passing through these. Now if we consider this circle to be the intersection of some plane with our desired sphere, it's clear that we can grow or shrink the sphere (and orient it to either side of the plane) so that it incorporates the remaining point.

Algorithmically, the aforementioned link gives you plenty of ideas to work with.

Regards

##### Share on other sites
Zipster    2359
Yeah I'm silly, for some reason my mind was focusing too much on the degenerate 2D coplanar case to realize that in the general 3D case each triplet of points would lie on the circumference of a circular cross section of the sphere. I'm just no good with algorithms I can't draw on paper [smile]

##### Share on other sites
alvaro    21246
Quote:
 Original post by TheAdmiralWe can picture it this way:Pick any three points. We can create a unique circle passing through these. Now if we consider this circle to be the intersection of some plane with our desired sphere, it's clear that we can grow or shrink the sphere (and orient it to either side of the plane) so that it incorporates the remaining point.

Funny. That's exactly how I figured out that a solution must exist. Then I just googled a little and I found that link.

##### Share on other sites
Raghar    96
Quote:
 Original post by daliYeah thats true. I need this for making a 3d delaunay triangulation to find out if one point is inside the sphere of the tet. The solution should be very fast and should make nearly correct results.

Let say you have a sphere with minimal volume that contains all four points, let say that you need to encapsulate a non degenerate tetrahedron. Now answer the question: How many points must be part of the surface of the sphere at minimum?

##### Share on other sites
Let say you have a sphere with minimal volume that contains all four points, let say that you need to encapsulate a non degenerate tetrahedron. Now answer the question: How many points must be part of the surface of the sphere at minimum?

----

I'm guessing 2, considering the case of a very long thin tetrahedron.