Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Recolector de Cienci...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Recolector de Ciencia Abierta, RECOLECTA
Bachelor thesis . 2016
License: CC BY NC ND
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Recolector de Ciencia Abierta, RECOLECTA
Bachelor thesis . 2016
License: CC BY NC ND
versions View all 1 versions
addClaim

Diagrama de potencias

Authors: Martín Santos, Tomás;

Diagrama de potencias

Abstract

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.

Keywords

Matemáticas

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green