CBL - Campus del Baix Llobregat

Projecte llegit

Títol: Angles obtusos en conjunts de punts - un problema de Geometria combinatòria

Director/a: HUEMER, CLEMENS

Departament: MAT

Títol: Angles obtusos en conjunts de punts - un problema de Geometria combinatòria

Data inici oferta: 29-01-2013 Data finalització oferta: 29-09-2013

Estudis d'assignació del projecte:

GR ENG SIS TELECOMUN

GR ENG TELEMÀTICA

Tipus: Individual

Lloc de realització: EETAC

Paraules clau:
Geometria, Combinatòria

Descripció del contingut i pla d'activitats:
Este proyecto abarca un problema clásico de la Geometría combinatoria, el del estudio de ángulos obtusos (ángulos mayores a π/2 radianes) en un conjunto de puntos en el plano. La pregunta central es: ¿Cuál es la cantidad mínima de ángulos obtusos que siempre hay en una nube de n puntos?. En todo momento se verificará que tres puntos no sean co-lineales (formaciones de tres puntos con ángulo de π radianes). Este problema fue estudiado por Conway, Croft, Erdös y Guy en su trabajo On the distribution of values of angles determined by coplanar points del año 1979, donde determinaron cotas para este mínimo número de ángulos obtusos entre todas las nubes de n puntos. En la tesis presente se da una aproximación computacional al problema. En primer lugar, se presentan las demostraciones de Conway. Además se ha implementado un programa para comprobar la buena cualidad de estas cotas. También se cuenta el número de ángulos obtusos en conjuntos de puntos aleatorios, verificando el valor esperado de ángulos obtusos, determinado de manera teórica por E. Langford en 1970. En la parte central del proyecto se estudia el efecto de transformaciones geométricas al número de ángulos obtusos en nubes de puntos. Las funciones consideradas incluyen: la transformada de Möbius, la función exponencial y la función Shear entre otras. Se presentan resultados experimentales sobre cuáles de las transformadas tienden a disminuir el número de ángulos obtusos si son aplicadas sobre conjuntos de puntos aleatorios. Además, se estudia el grado de reducción de ángulos obtusos, que mide cuanto disminuye el número de ángulos obtusos al aplicar una cierta transformada a un conjunto de puntos. Finalmente se contempla la opción de combinar varias transformadas para generar nubes de puntos con pocos ángulos obtusos. Las distintas pruebas del proyecto han sido realizadas con el programa MATLAB.

Overview (resum en anglès):
This project treats a classic problem in combinatorial geometry: the study of obtuse angles (angles larger than pi/2 radians) in a set of points on the plane. The main question is: What is the minimum number of obtuse angles that are determined by any set of n points? This problem was studied by Conway, Croft, Erdös and Guy in their work On the distribution of values of angles determined by coplanar points in the year 1979, where they could determine bounds on the minimum number of obtuse angles among all point clouds with n points. This thesis presents a computational approach to the problem. In the first place, these proofs of Conway et al. are discussed. Furthermore, a program to verify the good quality of these bounds has been implemented. Also the expected number of obtuse angles in a random point set, which was determined by E. Langford in 1970, is confirmed by means of experiments. The central part of the project studies the effect of geometrical transformations on the number of obtuse angles in a given point cloud. The considered functions include: the Möbius transformation, the exponential function, and the shear transformation, among others. We present experimental results on the question: Which of the considered transformations tend to decrease the number of obtuse angles, if applied to a random point set? Also, we study the degree of reduction of obtuse angles, which measures by how much the number of obtuse angles can be decreased if a specific transformation is applied to a point cloud. Finally, we combine some of the considered transformations in order to generate point clouds with few obtuse angles. The different experiments in this project have been carried out with the program MATLAB.