Ajuste de particiones planas mediante diagramas de Voronoi discretos

García Bernal, Daniel (2017). Ajuste de particiones planas mediante diagramas de Voronoi discretos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Ajuste de particiones planas mediante diagramas de Voronoi discretos
Author/s:
  • García Bernal, Daniel
Contributor/s:
  • Abellanas Oar, Manuel
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2017
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

La geometría computacional se centra en el diseño y análisis de algoritmos para problemas geométricos. En la última decada, esta disciplina ha atraído un enorme interés. Pero ha sido en los últimos a~nos cuando se ha incrementado el interés en una estructura geométrica, concretamente los diagramas de Voronoi. No solo por sus características y propiedades matemáticas, sino también por aparecer ampliamente relacionados con fenómenos y procesos físicos que se dan en la naturaleza. Los diagramas de Voronoi se construyen a partir de una simple idea, dado un número de puntos en el plano, el diagrama de Voronoi divide el plano según la regla del vecino más cercano: cada punto se asocia con la región del plano más cercano a él. En este trabajo, el objetivo consistirá en estudiar el proceso inverso, llamado Problema del Voronoi inverso (PVI). El PVI trata de, a partir de una partición de un plano dado, que es, o que se asemeja, a un diagrama de Voronoi, obtener los puntos generadores de este, y si no, aquellos de aquel diagrama de Voronoi que más se asemeje. Para resolver esto, se desarrollarán una serie de métodos heurísticos, como el método del Descenso más pronunciado y el método del recocido simulado, en código Python, con el fin de obtener una solución óptima, para posteriormente poder realizar un análisis y estudio de las soluciones obtenidas. Este estudio se realizará en el ámbito discreto, ya que las particiones a estudiar vendrán dadas en formato de imagen, es decir, una matriz mxn de píxeles. Esto conllevará a desarrollar un Generador de diagramas de Voronoi modificados, que se diseñará en la parte de preproceso de la aplicación, que permitirá obtener distintas particiones en formato de imagen para poder poner a prueba la aplicación desarrollada.---ABSTRACT---Computational geometry is concerned with the design and analysis of algorithms for geometrical problems. Computational geometry has attracted enormous research interest in the past decade. But it has been in the last years when the interest towards the geometric stucture, called Voronoi diagrams. has increased. Those diagrams recevie so much attention due to their mathematical properties and their appearance in diferent phenomena and process in the nature. Constructing a Voronoi diagram just needs a simple idea. Given a certain number of points in the plane, their Voronoi diagram divides the plane according to the nearest-neighbor rule: Each point is associated with the region of the plane closest to it. In this project, the objective will be to study the inverse process, called Inverse Voronoi problem (IVP). The IVP consists of obtaining the generators points of a Voronoi diagram which matches, or it is similar, to a given partition. In order to resolve this problem, it will have to developed a number of heuristic methods, such as: Method of steepest descent and simmulated annealing; in Python code, so that an optimal solution can be obtained, to later, perform an analysis and study of those solutions. This study will be developed in a discrete scope, because the partitions will be given in the format of an image, in other words, a matrix mxn of pixels. It will carry the development of a modify Voronoi diagrams Generator, designed in preprocessign phase of the application, that will permit to get several partitions in the format of an image in order to test the application.

More information

Item ID: 47124
DC Identifier: http://oa.upm.es/47124/
OAI Identifier: oai:oa.upm.es:47124
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 04 Jul 2017 06:56
Last Modified: 04 Jul 2017 06:56
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM