Finding the union of N random circles arbitrarily (or conspiratorially) placed on a two-dimensional surface

Question

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)...

Answer 1

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

Answer 2

I believe Herbert Edelsbrunner has written a few papers on the topic (for balls in $\mathbb{R}^d$), though his main interest was in d=3. You might try starting with "The union of balls and its dual shape", which discusses some structure useful in all dimensions.

Answer 3

I would perform DFS on a quadtree to the desired level of depth. Can't prove it is optimal, but it is very space efficient and can be done in parallel.

At each level you need to determine::
  If one of the circles does not touch this box then I return empty.
  If all remaining circles cover this box then I return the size of the box.
  Any circles that cover this box I ignore them on future recursions. 

Answer 4

The problem was solved completely by the following papers:

A New Algorithm for Dynamic Computing the Perimeter of Union of Circular Arcs， CHEN Jian-xun ZHAO Hui Dept. of Computer Science & technology, Wuhan University of Science & Technology, Wuhan Hubei 430081; Journal of Computer-Aided Design & Computer Graphics，1998-03