Algoritmos de backtracking en la búsqueda de thrackles de triángulos maximales

Ponente(s): Santiago León Ortiz

Sea $S$ un conjunto de $n$ puntos en el plano, y sea $T$ un conjunto de triángulos con vértices en $S$ que no tienen aristas en común. Decimos que $T$ es un thrackle si cualquier par de triángulos comparte un vértice o alguna de sus aristas se intersecta. Presentamos varios algoritmos de backtracking relacionados con la búsqueda de thrackles de triángulos de tamaño máximo sobre conjuntos de $n$ puntos para valores pequeños de $n$.