Probar o refutar: cada polígono con un número par de vértices puede ser repartido por las diagonales en los cuadriláteros

Question

Pregunta:

Verdadero o Falso?

Cada polígono con un número par de vértices puede ser dividido por las diagonales en los cuadriláteros.

Detalles:

Cualquier polígono ortogonal puede ser dividido por las diagonales en cuadriláteros convexos. (La prueba está disponible en el capítulo 2 de la Galería de Arte "Teoremas y Algoritmos", por Joseph O'Rourke).

También sabemos que ortogonal de los polígonos que tienen número par de vértices.

Así, es natural suponer que todos los polígonos de tener un número par de vértices puede ser dividido por sus diagonales en los cuadriláteros. Es esto supongo que es verdad?

Nota: ya sé que hacer supongo que el más fuerte por el cambio de "cuadriláteros" a "cuadriláteros convexos" no es cierto, y tengo un contraejemplo para que. Pero todos los polígonos I empate podría ser dividido en cuadriláteros. Por lo tanto, si la conjetura es verdadera, probablemente debería proponer un algoritmo para hacer la partición, y si no, un contraejemplo.

Answer 1

La afirmación es falsa. Considere la posibilidad de este polígono de ocho lados:

Supongamos que el color de los vértices de cualquiera, incluso de lados del polígono de color negro o blanco. Entonces es fácil ver que cualquier quadrilateration (descomposición por las diagonales en cuadriláteros), si existe, debe utilizar las diagonales que conectan los vértices de enfrente de colores. Sin embargo, la única diagonales acostado en su totalidad dentro de este polígono son los bordes entre el interior de la plaza de los vértices, el último de los cuales todos deben tener el mismo color. Por lo tanto no quadrilateration es posible.

Una construcción similar muestra que tales indecomposable polígonos existen para cualquier número de lados sea mayor que 4.