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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

5 Comentarios

  1. Que bien! Me hace mucha ilusión! Sobre todo porque había participado ya en muchos desafíos.

    Creo que debo compartir el mérito con el otro concursante, al 50%!!

    Diamond, creo que por esta vez podría publicar la lista de todos los acertantes, no? 🙂

    La verdad es que me extraña la poca participación, sobre todo porque era un problema bonito y sin ninguna necesidad de conocimientos matamáticos.

    Espero que esta baja participación puntual no impida seguir con los desafíos.

    Saludos

    Publica una respuesta
  2. Creo que el otro concursante soy yo, salvo que el correo me jugara una mala pasada. Me llamo Pako y me gustan las matemáticas desde siempre. Participé en todos los desafíos de El País y en los de Gaussianos desde que tuve noticias de ellos. Del problema me interesa, sobre todo, el hecho de que no todas las 4-pseudotriangulaciones son construibles con el método y por tanto el método de coloreo tampoco es completo. Siempre aprende uno algo nuevo. Diamond, espero que sigas planteándonos tan apasionantes cuestiones. Cartesiano, enhorabuena!

    Publica una respuesta
  3. Efectivamente, el otro concursante era Francisco Pi. Enhorabuena para ti también por haber resuelto el desafío :).

    Publica una respuesta
  4. Gracias David!

    Tienes razón. Mi solución no contemplaba el caso que comentas, y por tanto la demostración del 2 punto no está completa.

    Es muy habitual que no interpretemos de forma totalmente correcta el enunciado (yo el primero de todos). Normalmente lo primero que entendemos se queda grabado a fuego como si fuera la verdad más absoluta.

    Yo decidí (por mi cuenta) que podía ir escogiendo los puntos en el orden que se me antojara, y no contemplé que me dieran una pseudotriangulación ya construida. Yo puedo demostrar que puedo escoger una ordenación determinada para obtener el mínimo, pero así no demuestro que es el mínimo de TODAS las soluciones.

    Es un problema bonito, pero lo mejor es que he aprendido lo que es un “pseudotriángulo”, y cómo no, a releer el enunciado correctamente.

    Felicidades también para ti Francisco Pi, sigue intentándolo como yo, al final cae el premio. 🙂

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Hace unas semanas que terminó el plazo para el envío de soluciones del Desafío…
  2. Resumen de la 4.1231056 edición del Carnaval de Matemáticas | SCIENTIA - […] Desafíos GaussianosyGuijarro – Desafío nº 10: “Pseudo-triángulos y pseudo-triangulaciones”… … en Gaussianos. […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *