How can I determine quickly how many points of given set does a sphere contains?

Question

Given a set of points in a form of (x, y, z), and a set of spheres in a form of (x, y, z, radius).

The goal is, for each sphere, to count the number of points within the sphere.

I compared the Euclidean distance of the center of the sphere and the point against the radius of the sphere, and this algorithm takes O(N*M) time complexity where N, M are the numbers of points and spheres respectively.

I tried to exclude points outside the box of (x ± r, y ± r, z ± r), but it doesn't improve the calculation time at all.

So I studied some data structures like segment tree, quadtree, octree & k-d tree, but I had a hard time applying them to my goal.

How can I downgrade the time complexity to O(NlogM), O(MlogN), or something else?

Answer 1

If coordinate ranges are limited, you can make space subdivision into equal cubes, and assign points to corresponding cubes (cells).

For every sphere you have to check only cells near this sphere (roughly large cube centered at sphere center).

Real gain depends on proper choice of cell size and point distribution.

Your mentioned k-d tree - it seems a good choice for this kind of problem.

(As example - using this approach for 2d problem of finding close pairs gave time gain 11466 ms => 62 ms(against pairwise comparison) for 64K points with rather uniform distribution)

Answer 2

You could try a sweepline strategy.

• sort the points by increasing height,

• sort the spheres by increasing height of the bottom point;

• scan space with an horizontal plane moving from point-to-point, while you maintain a list of the spheres intersected (a sphere enters the list when its bottom point has a lower Z and leaves it with its top point is lower);

• solve the 2D point-in-circle problem for the spheres in the active list.

This reduces the number of tests from NM to NL, where L is the average number of sphere in the active list. The total cost is O(N Log N+M Log M+NL). If the spheres occupy a small fraction of space, the saving can be significant.

For further speedup, you can arrange the spheres in a "hierarchy of bounding volumes", i.e. a tree of nested spheres. Then keep the sweepline strategy, while also entering the bounding spheres in the active list. Using the nesting links, you can accelerate the point-in-spheres queries. (A point not in a bounding sphere cannot lie inside any of the enclosed spheres.)