Clustering data based on the radius of a sphere

I have a data-set that has four columns [X Y Z C]. I would like to find all the C values that are in a given sphere centered at [X, Y, Z] with a radius r. What is the best approach to address this problem? Should I use the clusterdata command?

• It would be good to update this question with the size of the data set. – Bill Barth Dec 8 '12 at 3:22

To collect the required C values I'd make a single pass through the data-set (array?) with some quick checks to eliminate most of the points outside the sphere, and then (only for the points that seem eligible) a check of actual radius.

That is, for a candidate point (x_i,y_i,z_i,c_i), test:

1) Is x_i between X-r and X+r?
2) If so, is y_i between Y-r and Y+r?
3) If so, is z_i between Z-r and Z+r?

Only if all three tests are true is it possible for the point to be in the desired sphere. For the final test, use precomputed r^2 and ask:

4) Is (x_i - X)^2 + (y_i - Y)^2 + (z_i - Z)^2 less than or equal r^2 ?

If the point passes the final test, include c_i in your collected C values.

• Depending on how big is $r$ compared to the range of possible values, it may be more economical to do only three comparisons, the second and third being $(y_i-Y)^2 \leq r^2 - (x_i-X)^2$ and $(z_i-Z)^2 \leq r^2 - (x_i-X)^2 - (y_i-Y)^2$, which can be computed incrementally. – Jaime Dec 7 '12 at 1:04
• @Jaime: Interesting idea. The sphere takes up about 52% of its bounding cube, so assuming uniform distribution the "costly" part of radius testing (multiplications) is avoided about half the time in my scheme, where you do two of three multiplies (squarings) in the 2nd step. Either of our approaches would benefit from having the data-set sorted by (at least) one of the coordinates, so a binary search could be partially used in the first comparison. – hardmath Dec 7 '12 at 1:38