Campus del Baix Llobregat
 
Projectes oferts

Projectes matriculats

Tribunals i dates de lectura

Projectes llegits
(2012-2)

DG ENG AERO/SIS TEL

DG ENG AERO/TELEMÀT

DG ENG SISTE/TELEMÀT

ENG TELEC 2NCICLE 01

ET AERO/ETT SIST 05

ET AERONÀUTICA 03

ETT SIST/ ET AERO 05

ETT SIST TELEC 00

ETT SIST TELEC 91

ETT TELEMÀTICA 00

GR ENG AERONAVEGACIÓ

GR ENG AEROPORTS

GR ENG SIS TELECOMUN

GR ENG SIST AEROESP

GR ENG TELEMÀTICA

MU AEROSPACE S&T 09

MU DRONS

MU MASTEAM 2009

MU MASTEAM 2015

Cerca projectes

Calendari TFG de dipòsit i lectura

Documentació

Web UPC


 

Projecte llegit

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

Director: 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:
    ENG TELEC 2NCICLE 01
    ET AERONÀUTICA 03
    ETT SIST TELEC 00
    ETT TELEMÀTICA 00
    GR ENG AERONAVEGACIÓ
    GR ENG AEROPORTS
    GR ENG SIS TELECOMUN
    GR ENG TELEMÀTICA
    MU AEROSPACE S&T
    MU MASTEAM
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.


Data de generació 26/01/2021