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