Diagrama de potencias

Martín Santos, Tomás (2016). Diagrama de potencias. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: Diagrama de potencias
Autor/es:
  • Martín Santos, Tomás
Director/es:
  • Abellanas Oar, Manuel
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Junio 2016
Materias:
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (2MB) | Vista Previa

Resumen

Los Diagramas de Potencias (Power Diagrams) son una generalización de los Diagramas de Voronoi, que junto a la Envolvente Convexa son dos de las estructuras fundamentales dentro del ámbito de la Geometría Computacional. Para poder tener una noción correcta del Diagrama de Potencias, es necesario partir del Diagrama de Voronoi. Este tipo de estructuras geométricas están compuestas de regiones, tanto finitas como infinitas, que cubren todo el espacio en el que se estén calculando (en el caso concreto de este Trabajo Fin de Grado, será la recta y el plano). Cada región está generada por un punto denominado \generador". En el plano, una región está formada por los puntos más cercanos a un generador que a cualquier otro generador. Si el punto equidista de dos generadores, entonces pertenecerá a la frontera entre dos regiones. El cambio que introduce el Diagrama de Potencias es que, además de un punto generador, hay un peso asociado a cada punto, que representa el radio de una circunferencia de centro el punto generador. De esta forma, ahora las regiones no se definen por la distancia euclídea, como en el caso anterior, sino por la potencia de los puntos del plano respecto a las circunferencias, lo que define una nueva distancia. Esto hace que las regiones cambien, incluso puede ocurrir que un generador no tenga región asociada. El algoritmo que se emplea para calcular el Diagrama de Potencias (en el plano) se apoya en la técnica de la Dualidad Geométrica para calcular intersecciones de semiespacios. La Dualidad consiste en la identificación (dentro de la dimensión en la que se trabaje) de los parámetros de un punto (sus coordenadas) con los parámetros de un hiperplano (sus coeficientes), de forma que se puedan pasar de una forma a otra con una transformación muy simple. Además, el algoritmo trabaja en una dimensión superior con respecto a la cual se está calculando el diagrama. Para realizar la implementación de estos algoritmos y funciones se ha empleado la herramienta SageMath, que permite trabajar en el lenguaje SAGE. Este lenguaje está basado en Python e incorpora de serie una gran cantidad de librerías matemáticas. Aún así, ha sido necesario incluir alguna librería externa, necesaria para el desarrollo de este Trabajo Fin de Grado.---ABSTRACT---Power Diagrams are a generalization of Voroni Diagrams, which alongside with the Convex Hull, are two fundamental structures in the area of Computational Geometry. In order to have an accurate notion of Power Diagrams, it is necessary to start from Voronoi Diagrams. This kind of geometrical structures are made of regions, both finite and infinite, that cover all the space in which they are being computed (in this case, it would be the line and the plane). Each region is generated by a point called \generator". In the plane, a region is formed by the nearest points to a generator, rather than to any other generator. If the point is equidistant to two generators, then it will belong to the boundary between twio regions. The change introduced by Power Diagrams is that, besides the generator point, there is a weight associated to each point, which represents the radius of a circle that has the generator point as its center. Thus now the regions are not defined by the Euclidean distance as before, but by the power of the points in the plane in respect to the circles, which defines a new distance. This is why regions change, it may even happen that a generator does not have an associated region. The algorithm used to compute the Power Diagram (in the plane) rests on the Duality technique to compute intersections of half-spaces. The Duality consists in the identification (in the dimension we are working on) of the parameters of a point (its coordinates) with the parameters of a hyperplane (its coeficients), so that they can be change from one to another with a very simple transformation. Furthermore, the algorithm works in a superior dimension in relation to the one the diagram it is being computed. In order to implement this algorithms and functions, the tool SageMath has been used. This software allows to work in SAGE language. This language is based on Python and includes a big quantity of math libraries. However, it has been necessary to include some external libraries, needed to the development of this Final Dissertation.

Más información

ID de Registro: 42886
Identificador DC: http://oa.upm.es/42886/
Identificador OAI: oai:oa.upm.es:42886
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 18 Jul 2016 08:52
Ultima Modificación: 27 Oct 2016 07:50
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM