Desafíos GaussianosyGuijarro – Desafío nº 10: «Pseudo-triángulos y pseudo-triangulaciones» – Solución y ganador

Hace unas semanas que terminó el plazo para el envío de soluciones del Desafío GaussianosyGuijarro nº 10: Pseudo-triángulos y pseudo-triangulaciones, y hoy os traigo la solución del mismo y el ganador de Las mil caras de la belleza geométrica, de Claudi Alsina.

Sin duda éste ha sido el desafío más complicado de la serie, al menos teniendo en cuenta el número de soluciones que habéis enviado. Se han recibido la friolera de ¡¡2 respuestas!!, que resultaron ser correctas. A continuación recuerdo el enunciado del problema y os dejo la solución de David Orden, que fue el encargado de proponerlo:

Todos sabemos lo que es un triángulo, un polígono cerrado con tres vértices, y además sabemos que en esos tres vértices el ángulo interior es menor que 180 grados. Pero no tanta gente sabe lo que es un pseudo-triángulo, que se define como un polígono cerrado con tres vértices tal que el ángulo interior en cada uno de ellos es menor que 180 grados.

La figura muestra tres ejemplos de pseudo-triángulos; el de la izquierda es de hecho un triángulo, el del centro tiene cuatro lados y el de la derecha tiene ocho lados. La diferencia con el triángulo es que, además de los tres vértices con ángulo interior menor que 180 grados, en un pseudo-triángulo puede haber otros vértices, todos ellos con ángulo interior mayor que 180 grados (los ángulos iguales a 180 grados llevarían a casos degenerados, que vamos a descartar aquí).

Supongamos ahora que tenemos un conjunto P de puntos en el plano. De manera análoga a la definición de triangulación, podemos definir una pseudo-triangulación de P como una colección finita de pseudo-triángulos que usan sólo puntos de P y que cumplen dos condiciones:

1. No hay solapamientos, es decir, dados dos pseudo-triángulos o bien no se intersecan, o bien lo hacen en un punto de P, o bien lo hacen en un lado de un pseudo-triángulo.
2. La unión de esos pseudo-triángulos es la envolvente convexa de P (el convexo de menor área que lo contiene).

La figura muestra dos ejemplos de pseudo-triangulaciones; la de la izquierda es de hecho una triangulación, porque sólo usa triángulos (que son pseudo-triángulos de 3 lados), mientras que en la de la derecha se usan también pseudo-triángulos de 4 lados.

A este tipo de pseudo-triangulaciones que usan pseudo-triángulos de 3 ó 4 lados se les llama 4-pseudo-triangulaciones y de todas ellas nos vamos a centrar en las 4-pseudo-triangulaciones puntiagudas, aquéllas con la propiedad de que todos los puntos son puntiagudos, es decir, incidentes a algún ángulo mayor de 180 grados.

En la figura anterior, la de la derecha es una 4-pseudo-triangulación puntiaguda, mientras que la de la izquierda no lo es (de hecho, sólo los puntos exteriores son puntiagudos).

PREGUNTA 1: Si tenemos un conjunto de puntos dentro de un triángulo, ¿existe siempre una 4-pseudo-triangulación puntiaguda del conjunto total?

PREGUNTA 2: Supongamos que tenemos un conjunto de puntos dentro de un triángulo y una 4-pseudo-triangulación puntiaguda del conjunto total. Si queremos colorear los puntos de modo que no haya un segmento con ambos extremos del mismo color, ¿cuál es el menor número de colores con el que puede hacerse?

La solución propuesta por David es ésta:

Solución a la pregunta 1

Sí existe siempre. Para demostrarlo basta usar la siguiente construcción. Iremos insertando los puntos interiores en el triángulo, en un orden cualquiera.

• Si el nuevo punto está contenido en un triángulo, podemos unirlo con dos vértices cualesquiera del triángulo para obtener sendos pseudo-triángulos de tres y de cuatro lados.
• Si el nuevo punto está contenido en un pseudo-triángulo de cuatro lados, hay un único par de vértices del pseudo-triángulo a los que unir el nuevo punto para obtener dos pseudo-triángulos de cuatro lados (y que no aparezca uno de cinco lados).

La siguiente figura muestra los posibles casos:

Obervación: Si nos dan un conjunto de puntos, este método nos permite construir una 4-pseudo-triangulación puntiaguda, ¡¡pero no todas!! La del siguiente dibujo no se puede construir con este método:

Observa que cuando se usa el método el último vértice introducido siempre tiene exactamente 2 aristas incidentes. Pero en esta figura no hay ningún vértice así.

Solución a la pregunta 2

Las dos soluciones recibidas han resuelto la pregunta 2 dando la vuelta al método de la pregunta 1. Pero eso no sirve para una 4-pseudo-triangulación puntiaguda como la anterior, que no procede de ese método. Es una diferencia sutil y la solución válida no es muy diferente, así que no se lo hemos tenido en cuenta.

Por una parte, cualquier pseudo-triangulación se puede 4-colorear, ya que es un grafo plano y se puede aplicar el Teorema de los Cuatro Colores. Por otra parte, en nuestro caso es imposible usar sólo 2 colores, ya que la cara exterior es un triángulo y necesita al menos 3 colores. Así que la respuesta sólo puede ser 3 ó 4.

Vamos a ver que se puede conseguir colorear cualquier 4-pseudo-triangulación puntiaguda con 3 colores. Para ello será crucial la propiedad de que todos los puntos son puntiagudos. De este modo, cada punto interior será incidente a un ángulo de 180 grados en algún pseudo-triángulo de cuatro lados, que será su pseudo-triángulo asociado.

• Arrastramos cada punto interior sobre el vértice opuesto en su pseudo-triángulo asociado (el único vértice no adyacente a él).
• Repetimos el proceso hasta quedarnos sólo con el triángulo exterior, que coloreamos con 3 colores.
• Revertimos el proceso anterior y asignamos a cada vértice que va apareciendo el color de aquel vértice sobre el que lo habíamos arrastrado.

La siguiente figura muestra un ejemplo:

Observación: Arrastrar un punto incidente a 2 aristas, como en el ejemplo anterior, no da problemas. Sin embargo, arrastrar un punto incidente a más de 2 aristas podría dar lugar a situaciones degeneradas:

En la fila superior aparece, incidente a la base del triángulo exterior, un pseudo-triángulo de 4 lados degenerado (dos puntos se han fundido en uno solo). La buena noticia es que en estos casos degenerados se puede actuar igual que en los demás y, de este modo, el proceso funciona.

Referencias: La respuesta a la pregunta 1 aparece en el artículo «Tight degree bounds for pseudo-triangulations of points», de Kettner et al. La respuesta a la pregunta 2 aparece en el artículo «3-Colorability of Pseudo-Triangulations», de Aichholzer et al.

Y el ganador del desafío ha sido Cartesiano Caótico, que después de participar en casi todos los desafíos GyG que hemos propuestos al fin encuentra su recompensa. Pronto podrá disfrutar de Las mil caras de la belleza geométrica. Mi más sincera enhorabuena.

Esta es mi quinta aportación a la Edición 4.1231056 del Carnaval de Matemáticas, cuyo anfitrión es nuestro amigo José Manuel López Nicolás en su blog Scientia.