<p>See <a href="https://mathoverflow.net/questions/24859/finding-the-union-of-n-random-circles-arbitrarily-or-conspiratorially-placed-on">this earlier MathOverflow question</a>: the union of circles can be constructed (as its set of boundary arcs) in $O(n\log n)$ time. Once you have that, it's straightforward to use Green's theorem to calculate the area.</p>

CC BY-SA 3.0
2011-10-12T14:50:47.893Z
2011-10-12T14:50:47.893Z
2017-04-13T12:57:54.530Z
David Eppstein
<p>I have a set of $N$ circles with a set of known radii $r_i$ on a plane of some surface area $A$.  If intersection is allowed between circles, how can I most efficiently compute the exact (not approximate) surface area of their union?</p>

<cg.comp-geom>
Efficiently computing the exact union of 'N' intersecting circles on a plane
I.F.
# Efficiently computing the exact union of 'N' intersecting circles on a plane

(Asked by: username_0 on 2011-10-12)

I have a set of $N$ circles with a set of known radii $r\_i$ on a plane of some surface area $A$. If intersection is allowed between circles, how can I most efficiently compute the exact (not approximate) surface area of their union?

**Tags:** cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2011-10-12. Score: 6

See [this earlier MathOverflow question](https://mathoverflow.net/questions/24859/finding-the-union-of-n-random-circles-arbitrarily-or-conspiratorially-placed-on): the union of circles can be constructed (as its set of boundary arcs) in $O(n\log n)$ time. Once you have that, it's straightforward to use Green's theorem to calculate the area.


---

