Count number of points inside a circle fast

Question

Given a set of n points on plane, I want to preprocess these points somehow faster than O(n^2) (O(nlog(n)) preferably), and then be able to answer on queries of the following kind "How many of n points lie inside a circle with given center and radius?" faster than O(n) (O(log(n) preferably).

Can you suggest some data structure or algorithm I can use for this problem?

I know that such types of problems are often solved using Voronoi diagrams, but I don't know how to apply it here.

Answer 1

Build a KD-tree of the points, this should give you much better complexity than O(n), on average O(log(n)) I think.

You can use a 2D tree since the points are constrained to a plane.

Assuming that we have transformed the problem into 2D, we'll have something like this for the points:

 struct Node {
     Pos2 point;
     enum {
        X,
        Y
     } splitaxis;
     Node* greater;
     Node* less;
 };

greater and less contains points with greater and lesser coordinates respectively along the splitaxis.

 void
 findPoints(Node* node, std::vector<Pos2>& result, const Pos2& origin, float radius) {
     if (squareDist(origin - node->point) < radius * radius) {
         result.push_back(node->point);
     }
     if (!node->greater) { //No children
          return;
     }
     if (node->splitaxis == X) {
         if (node->point.x - origin.x > radius) {
             findPoints(node->greater, result, origin radius);
             return;
         }
         if (node->point.x - origin.x < -radius) {
             findPoints(node->less, result, origin radius);
             return;
         }
         findPoints(node->greater, result, origin radius);
         findPoints(node->less, result, origin radius);
     } else {
         //Same for Y
     }
 }

Then you call this function with the root of the KD-tree