Area of Union of $N$ Circle in a 2D plane.

general
, ,
1

Hello everyone,
I was solving this question on spoj. We have to find area of union of N circles. I Can do for 2 Circle(By finding sum of both circle area - intersection area) but could not Solve for N circle.

Can someone provide me with solution/a link to solution/an approach to solution?

P.S: I have also tried approximate integral. Code can be found here. This gives TLE.

Edit: i have found the solution. How to close this question?

2

smart !! :smiley:

3

Umm… I guess not enough! :slight_smile:

4

I have tried that(TLE). I have edited the answer.

1 Like
5

…XD

6

This can be solved using Green’s Theorem, with a complexity of n^2log(n).
If you’re not familiar with the Green’s Theorem and want to know more, here is the video and notes from Khan Academy. But for the sake of our problem, I think my description will be enough.
The general equation of Green’s Theorem is

\Huge\mathbf{\oint_{C} (Ldx + Mdy) = \iint_{R}(\frac{\partial M}{\partial x} - \frac{\partial L}{\partial y})dxdy}

If I put L and M such that

\huge\mathbf{\frac{\partial M}{\partial x} - \frac{\partial L}{\partial y} = 1}

then the RHS is simply the area of the Region R and can be obtained by solving the closed integral or LHS and this is exactly what we’re going to do.

All unions can be broken into such disjoint sets of circles which intersect
All unions can be broken into such disjoint sets of circles which intersect905Ă—791

So Integrating along the path in the anticlockwise gives us the Area of the region and integrating along the clockwise gives us negative of the Area. So

AreaOfUnion = (Integration along red arcs in anticlockwise direction + Integration along blue arcs in clockwise direction)

But the cool trick is if for each circle if we integrate the arcs which are not inside any other circle we get our required area i.e. we get integration in an anticlockwise direction along all red arcs and integration along all blue arcs along the clockwise direction. JOB DONE!!!

Even the cases when a circle doesn’t intersect with any other is taken
care of.

Here is the GitHub link to my C++ Code

2 Likes
7

nice approach! Thanks…

1 Like