# Vertices of intersection between N spheres

Just wanted to know what is the best algorithm (in terms of speed and accuracy) to determine the intersection of N spheres (in 3D). With intersection I mean the following; in 2D and in the case of two overlapping circles of finite radius R1 and R2, they will have two points P1 and P2 in common in the case that distance between centers C1 and C2 is smaller than R1+R2, so that if we trace lines starting from one of the centers to this two points, we get an isosceles triangle. If we add a new circle at C3 with radius R3, so that d31 (distance between sphere 3 and 1) is smaller thant R1+R3 and d32 smaller than R2 and R3, we will have 2 new points of the same "kind", let's call them P3 and P4. Now if we assume that P1 lies somewhere inside the three circles, the other points P2, P3 and P4 lie "outside". Using C1, C2 and C3, and P2, P3, and P4 we could easily calculate the surrounding line from the intersection between the three spheres. These "outside" points P2, P3 and P4 I call them vertices.

Now let's say we have N spheres and we move in the 3D world, how to fastly calculate these vertices?

-
Why do you need this for? Points of intersection between two spheres can be infinitely in number: intersection of two sphere is void, one point or one circle. The algorithm is just computational. There is no faster way, if the number of points is infinite. –  Beni Bogosel Jun 24 '11 at 11:29
ok, I rephrased the question, hope it gets more clear now –  flow Jun 24 '11 at 12:09
I didn't understand even the 2D version. With 3 circles there are six points of intersection, not four. I'm getting a feeling that in the 2D-case you want as the output the closed path $L$ consisting of line segments, where the centers $C_i$ and points of intersection $P_i$ alternate as end points, and you want $L$ to somehow be the `outer perimeter' in that all the other such line segments are inside the region with boundary formed by $L$. Is this correct? But still, Beni's point stands. In 3D there are no triangles, but cones. And cones don't have vertices, so I don't understand??? –  Jyrki Lahtonen Jun 26 '11 at 21:00
Had another idea/question: do you want the vertices to be points of intersection of three spheres in 3D, and the build a kind of polyhedron (consisting of tetrahedra as opposed to cones) out of those? Again keeping in mind that you only need the exterior faces of this polyhedral region of the 3D-space? –  Jyrki Lahtonen Jun 27 '11 at 20:07
Hi Jyrki, yes, that is the idea, but there are not three only spheres, but thousands of –  flow Jun 28 '11 at 5:22

My interpretation of your question: For spheres $S_i \subset \mathbb{R}^3$, find all points (vertices) $v_j$ which lie on the intersection of at least three.

I'm ignoring this inside/outside nomenclature - perhaps it won't be too hard to split up your $v_j$ into inside/outside groups once you have them - feel free to clarify.

The problem (I'm guessing here) is that when the size of your set of spheres $\{S_i\}_{i\le N}$ is large, the number of triples of spheres $N \choose 3$ is really large.

Still, computationally, what can you do? One straightforward optimization would be to split things up into disjoint (or sufficiently disjoint) clusters of spheres, if our $S_i$ are sparse enough in $\mathbb{R}^3$. But we're left with the main piece of work: Iterate over pairs, find the circles of intersection for those who are close enough, see if anyone else lies close enough to hit, and if so we've got a new pair of points to add to our $v_i$.

There's no trickery - we're not trying to figure out if two circles intersect in $\mathbb{R}^3$ - when the centers of a sphere and a circle are close enough, we're guaranteed that intersection.

-
You gave the best answer –  flow Jul 3 '11 at 21:31
I thought that finding the points of intersection is the easy part. As Ternary points out, the brute force method is no good given that $N \choose 3$ may be very large. Yet, I suspect that in a typical scenario the vast majority of spheres won't be intersecting. A possibly efficient way of reducing the workload is to sort the set of spheres in advance. Say, we store a sphere as a record $S_i=(x_i,y_i,z_i,r_i)$, where $(x_i,y_i,z_i)$ is the center and $r_i$ is the radius. Then sort the list of spheres according to the quantity $f(i)=x_i-r_i$. Then you can process the list to good effect in the sense that if you are studying the possible intersections with sphere $S_i$, then you can stop processing the list after $f(j)>x_i+r_i$.