Mixing
Prove or disprove: Every polygon with an even number of vertices may be partitioned by diagonals into quadrilaterals
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
Question:
True or False?
Every polygon with an even number of vertices may be partitioned by diagonals into quadrilaterals.
Details:
Any orthogonal polygon may be partitioned by diagonals into convex quadrilaterals. (The proof is available on chapter 2 of "Art Gallery Theorems and Algorithms", by Joseph O'Rourke).
We also know that orthogonal polygons have even number of vertices.
So, it's natural to guess that all polygons having an even number of vertices can be partitioned by their diagonals into quadrilaterals. Is this guess true?
Note: I already know that making the guess stronger by changing from "quadrilaterals" to "convex quadrilaterals" is not true and I have a counterexample for that. But all of the polygons I draw could be partitioned into quadrilaterals. So, if the guess is true, one should probably propose an algorithm to do the partitioning, and if not, a counterexample should be provided.
geometry
asked 3 hours ago
Arman Malekzadeh
1,738728
add a comment |Â
up vote
6
down vote
favorite
Question:
True or False?
Every polygon with an even number of vertices may be partitioned by diagonals into quadrilaterals.
Details:
Any orthogonal polygon may be partitioned by diagonals into convex quadrilaterals. (The proof is available on chapter 2 of "Art Gallery Theorems and Algorithms", by Joseph O'Rourke).
We also know that orthogonal polygons have even number of vertices.
So, it's natural to guess that all polygons having an even number of vertices can be partitioned by their diagonals into quadrilaterals. Is this guess true?
Note: I already know that making the guess stronger by changing from "quadrilaterals" to "convex quadrilaterals" is not true and I have a counterexample for that. But all of the polygons I draw could be partitioned into quadrilaterals. So, if the guess is true, one should probably propose an algorithm to do the partitioning, and if not, a counterexample should be provided.
geometry
asked 3 hours ago
Arman Malekzadeh
1,738728
Do you only consider simple polygons, or do you count polygons whose sides cross as well? And by quadrilaterals, you only talk about simple quadrilaterals, right?
– Zvi
3 hours ago
Hint: any polygon can be triangulated and two triangles define a quadrilateral.
– Yves Daoust
3 hours ago
@Zvi I only consider simple polygons and simple quadrilaterals :)
– Arman Malekzadeh
2 hours ago
@YvesDaoust, I don't see how your hint helps in finding a counterexample such as Parcly Taxel's. Could you elaborate on what you have in mind?
– Barry Cipra
2 hours ago
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
Question:
True or False?
Every polygon with an even number of vertices may be partitioned by diagonals into quadrilaterals.
Details:
Any orthogonal polygon may be partitioned by diagonals into convex quadrilaterals. (The proof is available on chapter 2 of "Art Gallery Theorems and Algorithms", by Joseph O'Rourke).
We also know that orthogonal polygons have even number of vertices.
So, it's natural to guess that all polygons having an even number of vertices can be partitioned by their diagonals into quadrilaterals. Is this guess true?
Note: I already know that making the guess stronger by changing from "quadrilaterals" to "convex quadrilaterals" is not true and I have a counterexample for that. But all of the polygons I draw could be partitioned into quadrilaterals. So, if the guess is true, one should probably propose an algorithm to do the partitioning, and if not, a counterexample should be provided.
geometry
asked 3 hours ago
Arman Malekzadeh
1,738728
Question:
True or False?
Every polygon with an even number of vertices may be partitioned by diagonals into quadrilaterals.
Details:
Any orthogonal polygon may be partitioned by diagonals into convex quadrilaterals. (The proof is available on chapter 2 of "Art Gallery Theorems and Algorithms", by Joseph O'Rourke).
We also know that orthogonal polygons have even number of vertices.
So, it's natural to guess that all polygons having an even number of vertices can be partitioned by their diagonals into quadrilaterals. Is this guess true?
Note: I already know that making the guess stronger by changing from "quadrilaterals" to "convex quadrilaterals" is not true and I have a counterexample for that. But all of the polygons I draw could be partitioned into quadrilaterals. So, if the guess is true, one should probably propose an algorithm to do the partitioning, and if not, a counterexample should be provided.
geometry
geometry
asked 3 hours ago
Arman Malekzadeh
1,738728
asked 3 hours ago
Arman Malekzadeh
1,738728
asked 3 hours ago
Arman Malekzadeh
1,738728
asked 3 hours ago
Arman Malekzadeh
1,738728
asked 3 hours ago
Arman Malekzadeh
1,738728
1,738728
Do you only consider simple polygons, or do you count polygons whose sides cross as well? And by quadrilaterals, you only talk about simple quadrilaterals, right?
– Zvi
3 hours ago
Hint: any polygon can be triangulated and two triangles define a quadrilateral.
– Yves Daoust
3 hours ago
@Zvi I only consider simple polygons and simple quadrilaterals :)
– Arman Malekzadeh
2 hours ago
@YvesDaoust, I don't see how your hint helps in finding a counterexample such as Parcly Taxel's. Could you elaborate on what you have in mind?
– Barry Cipra
2 hours ago
add a comment |Â
Do you only consider simple polygons, or do you count polygons whose sides cross as well? And by quadrilaterals, you only talk about simple quadrilaterals, right?
– Zvi
3 hours ago
Hint: any polygon can be triangulated and two triangles define a quadrilateral.
– Yves Daoust
3 hours ago
@Zvi I only consider simple polygons and simple quadrilaterals :)
– Arman Malekzadeh
2 hours ago
@YvesDaoust, I don't see how your hint helps in finding a counterexample such as Parcly Taxel's. Could you elaborate on what you have in mind?
– Barry Cipra
2 hours ago
Do you only consider simple polygons, or do you count polygons whose sides cross as well? And by quadrilaterals, you only talk about simple quadrilaterals, right?
– Zvi
3 hours ago
Do you only consider simple polygons, or do you count polygons whose sides cross as well? And by quadrilaterals, you only talk about simple quadrilaterals, right?
– Zvi
3 hours ago
Hint: any polygon can be triangulated and two triangles define a quadrilateral.
– Yves Daoust
3 hours ago
Hint: any polygon can be triangulated and two triangles define a quadrilateral.
– Yves Daoust
3 hours ago
@Zvi I only consider simple polygons and simple quadrilaterals :)
– Arman Malekzadeh
2 hours ago
@Zvi I only consider simple polygons and simple quadrilaterals :)
– Arman Malekzadeh
2 hours ago
@YvesDaoust, I don't see how your hint helps in finding a counterexample such as Parcly Taxel's. Could you elaborate on what you have in mind?
– Barry Cipra
2 hours ago
@YvesDaoust, I don't see how your hint helps in finding a counterexample such as Parcly Taxel's. Could you elaborate on what you have in mind?
– Barry Cipra
2 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
The statement is false. Consider this polygon on eight sides:
Suppose we colour the vertices of any even-sided polygon black or white. Then it is easy to see that any quadrilateration (decomposition by diagonals into quadrilaterals), if it exists, must use diagonals connecting vertices of opposite colours. Yet the only diagonals lying wholly within this polygon are the edges between the inner square of vertices, the latter of which must all have the same colour. Thus no quadrilateration is possible.
A similar construction shows that such indecomposable polygons exist for any even number of sides greater than 4.
answered 3 hours ago
Parcly Taxel
36.5k136994
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
The statement is false. Consider this polygon on eight sides:
Suppose we colour the vertices of any even-sided polygon black or white. Then it is easy to see that any quadrilateration (decomposition by diagonals into quadrilaterals), if it exists, must use diagonals connecting vertices of opposite colours. Yet the only diagonals lying wholly within this polygon are the edges between the inner square of vertices, the latter of which must all have the same colour. Thus no quadrilateration is possible.
A similar construction shows that such indecomposable polygons exist for any even number of sides greater than 4.
answered 3 hours ago
Parcly Taxel
36.5k136994
add a comment |Â
up vote
6
down vote
accepted
The statement is false. Consider this polygon on eight sides:
Suppose we colour the vertices of any even-sided polygon black or white. Then it is easy to see that any quadrilateration (decomposition by diagonals into quadrilaterals), if it exists, must use diagonals connecting vertices of opposite colours. Yet the only diagonals lying wholly within this polygon are the edges between the inner square of vertices, the latter of which must all have the same colour. Thus no quadrilateration is possible.
A similar construction shows that such indecomposable polygons exist for any even number of sides greater than 4.
answered 3 hours ago
Parcly Taxel
36.5k136994
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
The statement is false. Consider this polygon on eight sides:
Suppose we colour the vertices of any even-sided polygon black or white. Then it is easy to see that any quadrilateration (decomposition by diagonals into quadrilaterals), if it exists, must use diagonals connecting vertices of opposite colours. Yet the only diagonals lying wholly within this polygon are the edges between the inner square of vertices, the latter of which must all have the same colour. Thus no quadrilateration is possible.
A similar construction shows that such indecomposable polygons exist for any even number of sides greater than 4.
answered 3 hours ago
Parcly Taxel
36.5k136994
The statement is false. Consider this polygon on eight sides:
Suppose we colour the vertices of any even-sided polygon black or white. Then it is easy to see that any quadrilateration (decomposition by diagonals into quadrilaterals), if it exists, must use diagonals connecting vertices of opposite colours. Yet the only diagonals lying wholly within this polygon are the edges between the inner square of vertices, the latter of which must all have the same colour. Thus no quadrilateration is possible.
A similar construction shows that such indecomposable polygons exist for any even number of sides greater than 4.
answered 3 hours ago
Parcly Taxel
36.5k136994
edited 18 mins ago
answered 3 hours ago
Parcly Taxel
36.5k136994
answered 3 hours ago
Parcly Taxel
36.5k136994
answered 3 hours ago
Parcly Taxel
36.5k136994
36.5k136994
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%2f2960709%2fprove-or-disprove-every-polygon-with-an-even-number-of-vertices-may-be-partitio%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
Do you only consider simple polygons, or do you count polygons whose sides cross as well? And by quadrilaterals, you only talk about simple quadrilaterals, right?
– Zvi
3 hours ago
Hint: any polygon can be triangulated and two triangles define a quadrilateral.
– Yves Daoust
3 hours ago
@Zvi I only consider simple polygons and simple quadrilaterals :)
– Arman Malekzadeh
2 hours ago
@YvesDaoust, I don't see how your hint helps in finding a counterexample such as Parcly Taxel's. Could you elaborate on what you have in mind?
– Barry Cipra
2 hours ago