Best dynamic data structure for 2d circle nearest neighbor

Question 1

Thanks to @David Eisenstadt for the idea of a 3d search structure. This is part of the best answer, though his strange metric is not needed.

The key is to look in detail at how nearest neighbor search works. I'll show this for quadrees. Kd-trees with k=3 are similar. Here is pseudocode:

# Let nearest_info be a record containing the current nearest neighbor (or nil 
# if none yet) and the distance from point to that nearest neighbor.
def find_nearest_neighbor(node, target, nearest_info)
  if node is leaf
    update nearest_info using target and the points found in this leaf
  else
    for each subdivision S of node
      if S contains any point P where dist(P,T) < nearest_info.distance,
        find_neareast(S, target, nearest_info)
      end
    end
  end
end

When this is done, nearest_info contains the nearest neighbor and its distance.

The key is if S contains any point P where dist(P,T) < nearest_info.distance. In a 3d space, of (x,y,r) triples that describe circles, we have

def dist(P,T)
  return sqrt( (P.x - T.x)^2 + (P.y - T.y)^2 ) - P.r - T.r 
end

Here P is an arbitrary point in an octant of an octree cuboid. How to consider all points in the cuboid? Note all components of T are effectively fixed for a given search, so it's clearer if we write the target as a constant point (a, b, c):

def dist(P)
  return sqrt( (P.x - a)^2 + (P.y - b)^2 ) - P.r
end

Where we have left out c = T.r completely because it can be subtracted out of the minimum distance after the algorithm is complete. In other words, the radius of the target does not affect the result.

With this it is pretty easy to see that the P we need to obtain minimum dist to the cuboid is Euclidean closest to the target with respect to x and y and with the max represented radius. This is very easy and quick to compute: a 2d point-rectangle distance and a 1d max operation.

In hindsight all this is obvious, but it took a while to see it from the right point of view. Thanks for the ideas.

Question 2

Cover trees are another possibility for a proximity structure. They don't support deletes (?), but you can soft delete and rebuild in the background to keep the garbage from piling up, which may be a useful technique for the other structures.

There's a reduction from the 2D circle problem to the 3D point problem with a funky metric that goes like this. (The proximity structures that you named should be adaptable.) Map a circle centered at (x, y) with radius r to the point (x, y, r). Define the length of a vector (dx, dy, dz) to be sqrt(dx**2 + dy**2) + abs(dz). This induces a metric. To find the circle nearest to a center (x, y) (the radius of the query circle is not relevant), do a proximity search at (x, y, R), where R is greater than or equal to the maximum radius of a circle (it may be possible to modify your proximity structure so that it's not necessary to track R).

From my experience implementing kd-trees and Voronoi diagrams on points, it will be significantly easier to implement kd-trees from scratch. Even if you reuse someone else's robust geometric primitives (and please do, to save your sanity if you go this route), the degenerate edge cases of Voronoi/point location take time to get right.

Question 3

I propose the following heuristic using a KD-Tree or something else that allows for O(log N) nearest neighbor. Instead of using a single point and a radius to represented a circle. Use k equidistant points on a circle itself, plus the center of the circle, otherwise you might have issues with a small circle inside of a large circle. It's the same the same idea as using a regular polygon of k vertices to represent a circle. It is then possible to take one vertex and find it's nearest neighbor (ignoring the vertices on the same circle) to find an approximation as to what is the closest circle based on the closest regular polygon.

The performances are as followed:

Create the KD-Tree: O(kN log kN)

Remove/add Circle to KD-Tree: O(k log kN) -Add or remove all k points of a circle within the KD-Tree

Nearest Circle query (Circle): O(k log kN) -This is done by first removing all k points of the circle (O(k log kN)) as it's not terribly useful to find out that the nearest neighbor of a circle is unsurprisingly, the circle itself. Then for each k points in the circle, find the nearest neighbor (O(k log kN)). Once the nearest neighbors are found, the actual nearest (to within some error) is the the one with the smallest distance (after calculating the true distance based on point and radius) (O(1)).

I'd suggest either using k = log(N) if you prefer it to be fast or k = sqrt(N) if you prefer it to be accurate.

Also, it's possible I haven't considered some special case that causes issues, so watch out for them.

Question 4

If there is a guarantee that circles don't have large radius, at least that maximum radius (R) is significantly smaller than area where circles are positioned, than I think it can be covered with standard space partitioning and nearest neighbour search.

When searching for circle in a set that has minimal distance to given circle, than radius of given circle doesn't matter (distance definition.) Because of that it is same if only center (point) is compared to set of circles.

With that it is enough to store set of circles in space partition structure only by there centers (set of points.) Circle adding and deleting is done in standard way for points. Finding of nearest circle to given point can be done in two step:

find nearest center to given point P. Say circle C with center c and radius r.
center of circle that is closer to P, by your distance, can be only in ring around P with inner radius r and outer radius R-d(P,c). It is enough to search partitions that intersect that ring for candidates.

It is possible to optimize search by combining these two steps. In first step, some of partitions of interest are already visited. By storing which partitions are visited, and circle with minimal distance found in these partitions, search in second step can be reduced.