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.

  • 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 Oct 18 at 13:26
  • Hint: any polygon can be triangulated and two triangles define a quadrilateral. – Yves Daoust Oct 18 at 13:33
  • @Zvi I only consider simple polygons and simple quadrilaterals :) – Arman Malekzadeh Oct 18 at 13:55
  • 2
    @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 Oct 18 at 14:40
up vote 10 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.

  • Why doesn't this work? My Attempt – David Culbreth Oct 18 at 20:08
  • @DavidCulbreth diagonals can't cross. Alternatively, the point where those diagonals cross is not a vertex of the polygon. – Parcly Taxel Oct 18 at 23:05

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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