Exclusive disjunction of rectilinear polygons
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Polygons all of whose edges meet at right angles are called rectilinear polygons. Furthermore, lets assume integer coordinates at each point. The question is: Can we give an upper bound about the number of the area components created? An area component is a rectilinear polygon whose area belongs exclusively in the one of the two polygons (red areas):
.
For simplicity we can assume each polygon to be non self intersecting (wikipedia figure 1, bottom right excluded), but I would prefer to answer the general question. My feeling is that it should be the max of the two numbers of edges. Any insight/tip is welcome.
geometry computational-geometry polygons
asked Sep 3 at 13:37
Paramar
253111
add a comment |Â
up vote
1
down vote
favorite
Polygons all of whose edges meet at right angles are called rectilinear polygons. Furthermore, lets assume integer coordinates at each point. The question is: Can we give an upper bound about the number of the area components created? An area component is a rectilinear polygon whose area belongs exclusively in the one of the two polygons (red areas):.
For simplicity we can assume each polygon to be non self intersecting (wikipedia figure 1, bottom right excluded), but I would prefer to answer the general question. My feeling is that it should be the max of the two numbers of edges. Any insight/tip is welcome.
geometry computational-geometry polygons
asked Sep 3 at 13:37
Paramar
253111
Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons.
– gandalf61
Sep 3 at 16:06
Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though
– Paramar
Sep 3 at 17:39
I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all.
– gandalf61
Sep 4 at 9:09
yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate
– Paramar
Sep 4 at 9:57
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Polygons all of whose edges meet at right angles are called rectilinear polygons. Furthermore, lets assume integer coordinates at each point. The question is: Can we give an upper bound about the number of the area components created? An area component is a rectilinear polygon whose area belongs exclusively in the one of the two polygons (red areas):.
For simplicity we can assume each polygon to be non self intersecting (wikipedia figure 1, bottom right excluded), but I would prefer to answer the general question. My feeling is that it should be the max of the two numbers of edges. Any insight/tip is welcome.
geometry computational-geometry polygons
asked Sep 3 at 13:37
Paramar
253111
Polygons all of whose edges meet at right angles are called rectilinear polygons. Furthermore, lets assume integer coordinates at each point. The question is: Can we give an upper bound about the number of the area components created? An area component is a rectilinear polygon whose area belongs exclusively in the one of the two polygons (red areas):.
For simplicity we can assume each polygon to be non self intersecting (wikipedia figure 1, bottom right excluded), but I would prefer to answer the general question. My feeling is that it should be the max of the two numbers of edges. Any insight/tip is welcome.
geometry computational-geometry polygons
geometry computational-geometry polygons
asked Sep 3 at 13:37
Paramar
253111
asked Sep 3 at 13:37
Paramar
253111
asked Sep 3 at 13:37
Paramar
253111
asked Sep 3 at 13:37
Paramar
253111
asked Sep 3 at 13:37
Paramar
253111
253111
Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons.
– gandalf61
Sep 3 at 16:06
Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though
– Paramar
Sep 3 at 17:39
I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all.
– gandalf61
Sep 4 at 9:09
yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate
– Paramar
Sep 4 at 9:57
add a comment |Â
Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons.
– gandalf61
Sep 3 at 16:06
Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though
– Paramar
Sep 3 at 17:39
I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all.
– gandalf61
Sep 4 at 9:09
yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate
– Paramar
Sep 4 at 9:57
Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons.
– gandalf61
Sep 3 at 16:06
Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons.
– gandalf61
Sep 3 at 16:06
Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though
– Paramar
Sep 3 at 17:39
Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though
– Paramar
Sep 3 at 17:39
I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all.
– gandalf61
Sep 4 at 9:09
I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all.
– gandalf61
Sep 4 at 9:09
yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate
– Paramar
Sep 4 at 9:57
yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate
– Paramar
Sep 4 at 9:57
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
After asking an expect, this question seem to be common knowledge for people in the comp. geometry field. The bound is quadratic at worst(for n and m edges of the 2 polygons we can have O(n*m) segments, and there is a construction that makes the bound tight) and the example follows: 
It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.
answered Sep 5 at 13:41
Paramar
253111
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
After asking an expect, this question seem to be common knowledge for people in the comp. geometry field. The bound is quadratic at worst(for n and m edges of the 2 polygons we can have O(n*m) segments, and there is a construction that makes the bound tight) and the example follows:
It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.
answered Sep 5 at 13:41
Paramar
253111
add a comment |Â
up vote
1
down vote
accepted
After asking an expect, this question seem to be common knowledge for people in the comp. geometry field. The bound is quadratic at worst(for n and m edges of the 2 polygons we can have O(n*m) segments, and there is a construction that makes the bound tight) and the example follows:
It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.
answered Sep 5 at 13:41
Paramar
253111
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
After asking an expect, this question seem to be common knowledge for people in the comp. geometry field. The bound is quadratic at worst(for n and m edges of the 2 polygons we can have O(n*m) segments, and there is a construction that makes the bound tight) and the example follows:
It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.
answered Sep 5 at 13:41
Paramar
253111
After asking an expect, this question seem to be common knowledge for people in the comp. geometry field. The bound is quadratic at worst(for n and m edges of the 2 polygons we can have O(n*m) segments, and there is a construction that makes the bound tight) and the example follows:
It is 2 "hair combs" with n and m teeth , and the one is rotated by 90 degrees.
answered Sep 5 at 13:41
Paramar
253111
edited Sep 5 at 13:50
answered Sep 5 at 13:41
Paramar
253111
answered Sep 5 at 13:41
Paramar
253111
answered Sep 5 at 13:41
Paramar
253111
253111
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2903867%2fexclusive-disjunction-of-rectilinear-polygons%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Since each "area component" in your examples has either two vertices from one polygon or one vertex from each polygon, my guess would be the maximum number of area components is half the total number of vertices in the two polygons.
– gandalf61
Sep 3 at 16:06
Can you make your argument a bit more concrete? Like a proof sketch? Intuition-wise I think you are right though
– Paramar
Sep 3 at 17:39
I've had second thoughts - I think I have found a counterexample to my hypothesis ! If you consider an L-shaped polygon (6 vertices) and a rectangle, I think the maximum number of area components is 4, not 5. So "half the total number of vertices" is not correct after all.
– gandalf61
Sep 4 at 9:09
yes it is 4, but you meant, up to half. Am I right? After all, I am asking for the upper bound. The exact number varies a lot, as the area components are not necessarily square. In any case, if you have a suggestion for a full proof, do not hesitate
– Paramar
Sep 4 at 9:57