Search code examples
javacomputational-geometry

Checking if an arbitrary circle contains more than k points of a given pointset

I have a Set of n points and a more or less arbitrary circle. Now I want to check if the circle contains at most k of the points.

Right now I'm just brute force testing all of the points. Since I need to answer this question for a lot of circles, a preprocessing time of up to n²log(n) would be fine.

The optimal data structure would most likely be the order k-Voronoi Diagram (not the one for dimension k), but I would need to implement it myself and therefore I would like to know if I have other (simpler) options.

Another Idea for some speed up would be using a KD-Tree.

I would like to know, if I'm missing another way to do it.

Solution

  • It seems that you are after a fixed-radius near-neighbor count query.

    Using a KD-tree (K=2), you can list the points in a given circle, in time roughly O(k + Log n). This is achieved by overlapping the circle with the rectangles of the KD-tree subdivision. When a rectangle is wholly contained in the circle, there is no need to subdivide further, all points inside the rectangle are inside the circle.

    So you can enhance the tree with the number of points contained in every node of the tree. This will lower the running time to O(m + Log n) where m is the number of rectangles contained in or split by the circle. It is also possible to stop subdividing when a rectangle contains less than a predefined number of points, and test them by brute force.

    These are heuristics. You have to test them on your cases to see if they are worth.

    enter image description here

    Update:

    Just an idea, not really investigated: Vantage-point trees are appropriate for k-nearest-neighbors searches and they partition the plane using circles. That might better blend with circle queries.

    https://en.wikipedia.org/wiki/Vantage-point_tree#Searching_through_a_vantage-point_tree