An implementation of Sharir's or Aurenhammer's deterministic algorithm for calculating the intersection/union of 'N' circles

Question

The problem of finding the intersection/union of 'N' discs/circles on a flat plane 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.

Since then, in 1985, Micha Sharir presented an O(n log2n) 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 a more efficient O(n log n) time and O(n) space algorithm for circle 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.

Earlier in 1983, Paul G. Spirakis also presented an O(n^2) time deterministic algorithm, and an O(n) probabilistic algorithm: Spirakis, P.G. Very Fast Algorithms for the Area of the Union of Many Circles. Rep. 98, Dept. Comput. Sci., Courant Institute, New York University, 1983.

---

I've been searching for any implementations of the algorithms above, focusing on computational geometry packages, and I haven't found anything yet. As neither appear trivial to put into practice, it would be really neat if someone could point me in the right direction!

Perhaps a constructive solid geometry (CSG) package would have a surface-area feature for overlapping circle primitives?

Answer 1

I've spent some time looking at the algorithms for computing the union of a set of balls - as you mention, it is done by using generalized Voronoi diagrams.

The CGAL library has a package that implements a union of balls. This is one dimension higher than what you're interested in, and it doesn't handle intersections. so probably no cigar.

If you're working in 2 dimensions, the problem is equivalent to finding a convex hull in 3 dimensions. You could use the convex hull stuff from CGAL or another package.

If you're looking for implementations of the specific algorithms you've mentioned, I can't help you. But if you just want to find the power diagram that allows you to easily compute unions and intersections, it might be easier than you think to roll your own using a 3D convex hull algorithm.

Sorry for the half baked answer, but we may as well start somewhere and see how much flexibility you have.

Edit: There's also a CGAL package for 2D power diagrams: http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html.

Also, @RGrey has found a CGAL library for calculating 2D booleans for generalized polygons, including circles at http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html.

Answer 2

There is no 2D power diagram implementation in CGAL. The link suggested above (http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html) is for the additive weighted Voronoi diagram, which uses the euclid + weight, instead of euclid^2 + weight (as Power Diagrams do).