Técnicas metaheurísticas para la maximización de la región de Voronoi

Abstract

La Geometría Computacional es una rama de la geometría que consiste en la elaboración de técnicas y herramientas para resolver problemas de naturaleza geométrica. Una de las estructuras más conocidas de la Geometría Computacional son los diagramas de Voronoi. Estos diagramas son subdivisiones del espacio asociando a cada punto del conjunto los puntos que se encuentren más cerca de un punto que de cualquier otro. El problema que se estudia en este proyecto es encontrar un nuevo punto tal que al introducirlo en el diagrama la región de área asociada a dicho punto en el nuevo diagrama generado sea máxima. Este proyecto tiene como objetivo principal el desarrollo de un software gráfico interactivo que permita realizar diagramas de Voronoi y obtener un nuevo punto que maximice la región de Voronoi. Para ello, esta herramienta utiliza técnicas heurísticas como son: Random Search, Simulated Annealing y Ant Systems para obtener una solución lo más cercano al óptimo posible. Por último, se ha realizado un estudio de los diversos resultados obtenidos con los algoritmos (tiempo de ejecución, porcentaje de área obtenida y velocidad de convergencia). Este análisis permite al usuario la posibilidad de escoger un algoritmo en función de los parámetros que considere más relevantes para el proyecto. Esta herramienta puede ser utilizada para dar solución a problemas de la actualidad, desde problemas para posicionamiento de nuevas antenas de telefonía a la posibilidad de darle a un robot la capacidad para moverse de forma autónoma.

Computational Geometry is a branch of geometry that consists of the development of techniques and tools to solve problems of geometric nature. One of the best-known structures of Computational Geometry are the Voronoi diagrams. These diagrams are subdivisions of the space associating to each point of the set the points that are closer to a point than to any other. The problem studied in this project is to find a new point such that when introduced in the diagram the area region associated to that point in the new generated diagram is maximal. The main objective of this project is the development of an interactive graphic software that allows to make Voronoi diagrams and to obtain a new point that maximizes the Voronoi region. For this purpose, this tool uses heuristic techniques such as: Random Search, Simulated Annealing and Ant Systems to obtain a solution as close to the optimum as possible. Finally, a study of the different results obtained with the algorithms (execution time, percentage of area obtained and convergence speed) has been carried out. This analysis allows the user to choose an algorithm according to the parameters considered most relevant to the project. This tool can be used to solve current problems, from problems for positioning new telephone antennas to the possibility of giving a robot the ability to move autonomously.