MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

6 added 45 characters in body

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

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..above (neither appear trivial to put into practice)...

4 Added results from a literature search on the problem

While we can always perform a monte carlo sampling of coordinates on the plane (or over some defined lattice), is there an efficient analytical deterministic method of calculating the exact area given by the union of all $N$ circles?

Update - Would it be useful After a more extensive literature search (and thanks to construct "jc" for mentioning Edelsbrunner!), I was able to find a Voronoi diagram 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 two-dimensional coordinates defining the N circles? I'm imagining 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 a program like Edelsbrunner etpower diagrams (generalizations of Voronoi diagrams):Aurenhammer, F. al.'s Alpha Shapes http://biogeometry.duke.edu/software/alphashapes/math.htmlImproved 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...

3 added 10 characters in body