CBL - Campus del Baix Llobregat

Projecte llegit

Títol: Comptatge de triangles en conjunts de punts acolorits - un problema de la Geometria combinatòria

Estudiants que han llegit aquest projecte:

Director/a: HUEMER, CLEMENS

Departament: MAT

Títol: Comptatge de triangles en conjunts de punts acolorits - un problema de la Geometria combinatòria

Data inici oferta: 17-09-2012     Data finalització oferta: 17-04-2013


Estudis d'assignació del projecte:
    GR ENG SIS TELECOMUN
    GR ENG TELEMÀTICA
Tipus: Conjunt     Nombre d'estudiants per realitzar-ho: 2-3
 
Lloc de realització: EETAC
 
Paraules clau:
Geometria combinatòria, Triangles, Conjunts de punts
 
Descripció del contingut i pla d'activitats:
Un objeto clásico de estudio en la Geometría combinatoria son conjuntos S de n puntos en el plano. Se dice que un triángulo con vértices en S esta vació si no contiene puntos de S en su interior. El número de triángulos vacíos depende de como se dibuja el conjunto S y una pregunta ardiente es: ¿Cuántos triángulos vacíos hay como mínimo en cada conjunto S de n puntos? Para descartar configuraciones de puntos degeneradas solo se consideran nubes de puntos sin tres puntos colineales.

En este proyecto se ha desarrollado un software que realiza el contaje de triángulos vacíos en un conjunto de n puntos colocados en el plano.
El software permite generar, visualizar gráficamente, buscar y mostrar las distribuciones de triángulos óptimas. Se considera la distribución óptima la que contiene menos triángulos vacíos.

El objetivo es acotar resultados teóricos mediante pruebas experimentales realizadas gracias al software creado.

El programa también permite contar triángulos vacíos monocromáticos en conjuntos de puntos bi-coloreados. Un triángulo monocromático es aquello cuyos tres vértices tienen el mismo color. Mientras que el primer problema ha sido muy bien estudiado durante las últimas décadas, la versión bi-coloreada queda para ser explorada en profundidad. En esta memoria también se exponen los resultados obtenidos sobre el mínimo número de triángulos vacíos en nubes (pequeñas) de puntos bi-coloreadas.

También se pone en contexto este problema con otros resultados relacionados, como el teorema de Erdös-Szekeres, y se da una pequeño resumen de otras problemas que han hecho grande la Geometria combinatoria.
 
Overview (resum en anglès):
A classical object of study in combinatorial geometry are sets S of points in the plane. A triangle with vertices from S is called empty if it contains no points of S in its interior. The number of empty triangles depends on the positions of points from S and a burning question is: How many empty triangles are there at least, among all sets S of n points? In order to discard degenerate point configurations, we only consider sets S without three collinear points.

In this project, a software has been developed which allows to count the number of empty triangles in a set of n points in the plane. The software permits generation of point sets and their graphical visualization, as well as searching and displaying of optimal point configurations encountered. A point set of a given cardinality is said to be optimal if it contains the minimum number of empty triangles.

The objective is to derive bounds on the minimum number of empty triangles by means of experiments realized with our software.

The created program also allows to count empty monochromatic triangles in two-colored point sets. A triangle is called monochromatic if its three vertices have the same color. While the first problem has been studied extensively during the last decades, the two-colored version remains to be explored in depth. In this work we also expose our results on the minimum number of empty triangles in (small) two-colored point sets.

Also, the treated problem is put in context with related results, such as the Erdös-Szekeres theorem, and a short outline of famous problems which contributed to the rise of combinatorial geometry is presented.


© CBLTIC Campus del Baix Llobregat - UPC