True or False?

Every polygon with an even number of vertices may be partitioned by diagonals into quadrilaterals.


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.

  • $\begingroup$ 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? $\endgroup$
    – user593746
    Oct 18 '18 at 13:26
  • $\begingroup$ Hint: any polygon can be triangulated and two triangles define a quadrilateral. $\endgroup$
    – user65203
    Oct 18 '18 at 13:33
  • $\begingroup$ @Zvi I only consider simple polygons and simple quadrilaterals :) $\endgroup$ Oct 18 '18 at 13:55
  • 2
    $\begingroup$ @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? $\endgroup$ Oct 18 '18 at 14:40

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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