4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

See this earlier MathOverflow question: 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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