8

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.

Community
  • 1
Arman Malekzadeh
  • 4,108
  • 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? –  Oct 18 '18 at 13:26
  • Hint: any polygon can be triangulated and two triangles define a quadrilateral. –  Oct 18 '18 at 13:33
  • @Zvi I only consider simple polygons and simple quadrilaterals :) – Arman Malekzadeh Oct 18 '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 '18 at 14:40

1 Answers1

12

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.

Parcly Taxel
  • 103,344