Find smallest enclosing circle

Question

On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known radii and positions with respect to the origin. (It is possible that some smaller sub-circles are partially or entirely inside some larger sub-circles.)

The entire plane is gridded uniformly into pixels with sides being horizontal and vertical (along coordinate axes). The size of the pixels is fixed and known a priori but otherwise much smaller than the size of parent circle; there are on the order of few $\times 10^{5}$ pixels all over the parent circle.

$\sim 1\%$ of the area of the parent circle is colored in the form of a few clumps across the parent circle covering $\sim 10^{3}$ pixels. These colored pixels are mostly inside sub-circles; all are entirely inside the parent circle. We are given the 2D Cartesian coordinates for (the centers of) all colored grids.

Each colored grid is associated with the smallest sub-circle that contains it. If the pixel falls within multiple sub-circles, only the smallest of the circles should be chosen.

Finally, I would like to calculate the total number of colored grids associated with each sub-circle. Is there an efficient algorithm for this?

Answer 1

Yes, there are efficient algorithms for this problem, using standard data structures for storing two-dimensional data.

Here is a simple approach. Store all of the colored pixels in a quadtree. Next, for each sub-circle, compute it bounding box, so now you have a square instead of a circle. Query the quadtree data structure to find all points contained within that square. For each such point, test whether it falls within the sub-circle. If it does, mark that point as associated with that sub-circle, unless it is already associated with a smaller sub-circle.

I expect the running time of this approach will be approximately $O(n+m)$ where $n$ is the number of colored points and $m$ is the number of sub-circles (assuming there is not too much overlap among the sub-circles, which seems likely to be the case for the parameter settings you listed). Thus, it should be very efficient.

You can alternatively replace the quadtree with any other data structure for 2D data, such as a k-d tree, though for the parameter sizes you mention, I expect that anything will already be quite fast and so it probably won't be necessary to worry too much about optimizing this as much as possible.