Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers

up vote 3 down vote accepted

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:

http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Voronoi_diagram_2/Chapter_main.html

share|improve this answer
add comment

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.

share|improve this answer
add comment

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. 
share|improve this answer
1  
Dear Chad, Thanks, I really appreciate you taking the time to answer my question! However, I'm looking for an exact/analytical solution to the problem... –  Rob Grey Jul 6 '10 at 3:12
add comment

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

share|improve this answer
    
Do you happen to have a version of this last paper in English? –  user23547 May 8 '12 at 19:23
    
"this last paper": Which paper? "Last" in this context does not pick out a paper unambiguously. –  Joseph O'Rourke May 8 '12 at 19:27
    
Sorry. I meant the paper "A New Algorithm for Dynamic Computing the Perimeter of Union of Circular Arcs", by CHEN Jian-xun and ZHAO Hui. The only related reference I found is en.cnki.com.cn/Article_en/CJFDTOTAL-JSJF803.004.htm but that is another paper (for union instead of perimeter) by CHEN Jian-xun and MA Heng Tai. I would like to see either of these papers by CHEN Jian-xun. Thanks! –  user23547 May 8 '12 at 20:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.