Please consider a two-dimensional surface populated with a set of Cartesian coordinates $(x_i, y_i)$ for $N$ circles with individual radii $r_i$, where $r_{\min} < r_i < r_{\max}$.
Here, the number of circles, $N$, may be large – ranging from hundreds to tens of thousands. The circles may sparsely populate the plane in some places, and in others, be 'conspiratorially' packed together. Furthermore, $r_{\min}$ / $r_{\max}$ are not necessary defined in such a way to allow for accurate convex hull, spline interpolation, etc.
While we can always perform a monte carlo sampling of coordinates on the plane (or over some defined lattice), is there an efficient deterministic method of calculating the exact area given by the union of all $N$ circles?
Update – After a more extensive literature search (and thanks to "jc" for mentioning Edelsbrunner!), I was able to find a few relevant papers in the literature. First, the problem was of finding the union of 'N' discs was first proposed by M. I. Shamos in his 1978 thesis:
Shamos, M. I. “Computational Geometry” Ph.D. thesis, Yale Univ., New Haven, CT 1978.
In 1985 Micha Sharir presented an $O(n \log^2n)$ time and $O(n)$ space deterministic algorithm for the disc intersection/union problem (based on modified Voronoi diagrams):
Sharir, M. Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14 (1985), pp. 448-468.
In 1988, Franz Aurenhammer presented another, more efficient O(n log n) time and O(n) space algorithm for circle (disc) intersection/union using power diagrams (generalizations of Voronoi diagrams):
Aurenhammer, F. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms 9 (1985), pp. 151-161.
It would be really neat if anyone could be point me to an implementation of one of the two determistic algorithms above, perhaps in a computational geometry package (neither appear trivial to put into practice)…
Best Answer
CGAL has a general Voronoi diagram module that's quite customizable. While I've never used it to build power diagrams, it should not be hard to add in the right kind of distance function to generate the diagrams you need:
https://doc.cgal.org/Manual/3.5/doc_html/cgal_manual/Voronoi_diagram_2/Chapter_main.html