Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted
+50

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.

share|improve this answer
    
You gave the best answer –  flow Jul 3 '11 at 21:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.