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.

Descripción

Título: Ajuste de particiones planas mediante diagramas de Voronoi discretos
Autor/es:
  • García Bernal, Daniel
Director/es:
  • Abellanas Oar, Manuel
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Junio 2017
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 (1MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 47124
Identificador DC: http://oa.upm.es/47124/
Identificador OAI: oai:oa.upm.es:47124
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 04 Jul 2017 06:56
Ultima Modificación: 04 Jul 2017 06:56
  • 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