Best dynamic data structure for 2d circle nearest neighbor

Question

The title is most of the problem. I have a set of circles, each given by a center C and radius r. The distance between two circles is the Euclidean distance between their centers minus both their radii. For circles a and b,

d_ab = |C_a - C_b| - r_a - r_b.

Note this can be negative if the circles overlap.

Then what is the quickest data structure for finding the nearest (minimum distance) neighbor of a given circle in the set?

Adding and deleting circles with "find nearest" queries interleaved in arbitrary order must be supported. Nothing is known about the set's geometric distribution in advance.

This will be the heart of a system where a typical number of circles is 50,000 and 10's of thousands of queries, inserts, and deletes will be needed, ideally at user-interaction speed (a second or less) on a high end tablet device.

The point nearest neighbor has been studied to death, but this version with circles seems somewhat harder.

I have looked at kd-trees, quad trees, r-trees, and some variations of these. Both advice on which of these might be the best to try and also new suggestions would be a terrific help.

Answer 1

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.

Answer 2

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.

Answer 3

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.