Mixing
Area of Union of n circles
$begingroup$
I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the set theory approach(inclusion-exclusion principle), where we know the formula for union of n sets. I was just using an operator Ar() which gives the area,i.e. Ar(A) gives me the area of A. I first tried to find out which circle is intersecting with which other circle(s) with the help of D<2R(D=dist between the centers of the two circles), then I was trying to calculate the area of intersection between them pairwise and hence find the area of union. But I am getting stuck for n>4. Can anyone provide a soln to this(soln by the set theory approach is necessary). Thanks in advance
geometry computational-geometry computational-mathematics
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
$endgroup$
add a comment |
$begingroup$
I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the set theory approach(inclusion-exclusion principle), where we know the formula for union of n sets. I was just using an operator Ar() which gives the area,i.e. Ar(A) gives me the area of A. I first tried to find out which circle is intersecting with which other circle(s) with the help of D<2R(D=dist between the centers of the two circles), then I was trying to calculate the area of intersection between them pairwise and hence find the area of union. But I am getting stuck for n>4. Can anyone provide a soln to this(soln by the set theory approach is necessary). Thanks in advance
geometry computational-geometry computational-mathematics
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
$endgroup$
add a comment |
$begingroup$
I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the set theory approach(inclusion-exclusion principle), where we know the formula for union of n sets. I was just using an operator Ar() which gives the area,i.e. Ar(A) gives me the area of A. I first tried to find out which circle is intersecting with which other circle(s) with the help of D<2R(D=dist between the centers of the two circles), then I was trying to calculate the area of intersection between them pairwise and hence find the area of union. But I am getting stuck for n>4. Can anyone provide a soln to this(soln by the set theory approach is necessary). Thanks in advance
geometry computational-geometry computational-mathematics
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
$endgroup$
I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the set theory approach(inclusion-exclusion principle), where we know the formula for union of n sets. I was just using an operator Ar() which gives the area,i.e. Ar(A) gives me the area of A. I first tried to find out which circle is intersecting with which other circle(s) with the help of D<2R(D=dist between the centers of the two circles), then I was trying to calculate the area of intersection between them pairwise and hence find the area of union. But I am getting stuck for n>4. Can anyone provide a soln to this(soln by the set theory approach is necessary). Thanks in advance
geometry computational-geometry computational-mathematics
geometry computational-geometry computational-mathematics
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
asked Jan 6 '12 at 4:20
SaptarshiSaptarshi
11
11
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
For the inclusion-exclusion approach, you need to be able to calculate for each set $S$ of circles the area $A_S$ of their intersection. Consider a set of circles, all of radius $1$, whose intersection is nonempty. The intersection will be a convex region bounded by $k$ arcs (where $k$ might be less than the number of circles); ignoring trivial cases, I'll suppose $kge 2$. Let $P_i = (x_i, y_i), i=0 ldots k$, be the endpoints of the arcs, taken counterclockwise, with (for convenience) $P_0 = P_k$. Note that the area of
the "cap" cut off from a circle of radius $1$ by a chord of length $L$ is
$f(L) = arcsin(L/2) - L sqrt{4 - L^2}/4$, while the area of the polygon
with vertices $P_i$ is $sum_{i=1}^k (x_{i-1} - x_i)(y_{i-1}+y_i)/2$.
So the total area of the intersection is
$$A_S = sum_{i=1}^k left( fleft(sqrt{(x_i - x_{i-1})^2 + (y_i - y_{i-1})^2}right) + frac{(x_{i-1} - x_i)(y_{i-1}+y_i)}2 right)$$
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
$endgroup$
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
add a comment |
$begingroup$
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
$$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 $$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
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
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f96839%2farea-of-union-of-n-circles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For the inclusion-exclusion approach, you need to be able to calculate for each set $S$ of circles the area $A_S$ of their intersection. Consider a set of circles, all of radius $1$, whose intersection is nonempty. The intersection will be a convex region bounded by $k$ arcs (where $k$ might be less than the number of circles); ignoring trivial cases, I'll suppose $kge 2$. Let $P_i = (x_i, y_i), i=0 ldots k$, be the endpoints of the arcs, taken counterclockwise, with (for convenience) $P_0 = P_k$. Note that the area of
the "cap" cut off from a circle of radius $1$ by a chord of length $L$ is
$f(L) = arcsin(L/2) - L sqrt{4 - L^2}/4$, while the area of the polygon
with vertices $P_i$ is $sum_{i=1}^k (x_{i-1} - x_i)(y_{i-1}+y_i)/2$.
So the total area of the intersection is
$$A_S = sum_{i=1}^k left( fleft(sqrt{(x_i - x_{i-1})^2 + (y_i - y_{i-1})^2}right) + frac{(x_{i-1} - x_i)(y_{i-1}+y_i)}2 right)$$
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
$endgroup$
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
add a comment |
$begingroup$
For the inclusion-exclusion approach, you need to be able to calculate for each set $S$ of circles the area $A_S$ of their intersection. Consider a set of circles, all of radius $1$, whose intersection is nonempty. The intersection will be a convex region bounded by $k$ arcs (where $k$ might be less than the number of circles); ignoring trivial cases, I'll suppose $kge 2$. Let $P_i = (x_i, y_i), i=0 ldots k$, be the endpoints of the arcs, taken counterclockwise, with (for convenience) $P_0 = P_k$. Note that the area of
the "cap" cut off from a circle of radius $1$ by a chord of length $L$ is
$f(L) = arcsin(L/2) - L sqrt{4 - L^2}/4$, while the area of the polygon
with vertices $P_i$ is $sum_{i=1}^k (x_{i-1} - x_i)(y_{i-1}+y_i)/2$.
So the total area of the intersection is
$$A_S = sum_{i=1}^k left( fleft(sqrt{(x_i - x_{i-1})^2 + (y_i - y_{i-1})^2}right) + frac{(x_{i-1} - x_i)(y_{i-1}+y_i)}2 right)$$
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
$endgroup$
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
add a comment |
$begingroup$
For the inclusion-exclusion approach, you need to be able to calculate for each set $S$ of circles the area $A_S$ of their intersection. Consider a set of circles, all of radius $1$, whose intersection is nonempty. The intersection will be a convex region bounded by $k$ arcs (where $k$ might be less than the number of circles); ignoring trivial cases, I'll suppose $kge 2$. Let $P_i = (x_i, y_i), i=0 ldots k$, be the endpoints of the arcs, taken counterclockwise, with (for convenience) $P_0 = P_k$. Note that the area of
the "cap" cut off from a circle of radius $1$ by a chord of length $L$ is
$f(L) = arcsin(L/2) - L sqrt{4 - L^2}/4$, while the area of the polygon
with vertices $P_i$ is $sum_{i=1}^k (x_{i-1} - x_i)(y_{i-1}+y_i)/2$.
So the total area of the intersection is
$$A_S = sum_{i=1}^k left( fleft(sqrt{(x_i - x_{i-1})^2 + (y_i - y_{i-1})^2}right) + frac{(x_{i-1} - x_i)(y_{i-1}+y_i)}2 right)$$
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
$endgroup$
For the inclusion-exclusion approach, you need to be able to calculate for each set $S$ of circles the area $A_S$ of their intersection. Consider a set of circles, all of radius $1$, whose intersection is nonempty. The intersection will be a convex region bounded by $k$ arcs (where $k$ might be less than the number of circles); ignoring trivial cases, I'll suppose $kge 2$. Let $P_i = (x_i, y_i), i=0 ldots k$, be the endpoints of the arcs, taken counterclockwise, with (for convenience) $P_0 = P_k$. Note that the area of
the "cap" cut off from a circle of radius $1$ by a chord of length $L$ is
$f(L) = arcsin(L/2) - L sqrt{4 - L^2}/4$, while the area of the polygon
with vertices $P_i$ is $sum_{i=1}^k (x_{i-1} - x_i)(y_{i-1}+y_i)/2$.
So the total area of the intersection is
$$A_S = sum_{i=1}^k left( fleft(sqrt{(x_i - x_{i-1})^2 + (y_i - y_{i-1})^2}right) + frac{(x_{i-1} - x_i)(y_{i-1}+y_i)}2 right)$$
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
answered Jan 6 '12 at 5:39
Robert IsraelRobert Israel
330k23219473
330k23219473
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
add a comment |
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $sum_{i=1}^k(Area of cap)_{i}$
$endgroup$
– Saptarshi
Jan 6 '12 at 9:40
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$
$endgroup$
– Robert Israel
Jan 6 '12 at 17:28
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Oh,ok...thanks a lot for your help
$endgroup$
– Saptarshi
Jan 7 '12 at 6:32
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
$begingroup$
Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance
$endgroup$
– Saptarshi
Jan 9 '12 at 4:13
add a comment |
$begingroup$
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
$$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 $$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
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
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
$endgroup$
add a comment |
$begingroup$
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
$$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 $$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
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
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
$endgroup$
add a comment |
$begingroup$
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
$$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 $$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
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
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
$endgroup$
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
$$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 $$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
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
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
edited Jan 30 at 2:24
Siong Thye Goh
103k1468120
103k1468120
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
answered Jan 30 at 2:03
Deepesh ThakurDeepesh Thakur
1
1
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f96839%2farea-of-union-of-n-circles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
