Juego de Voronoi dinámico

Abstract

Este trabajo se encuentra enmarcado en la conocida como Geometría Computacional, y trata con una estructura que es objeto de estudio de esta, los conocidos como Diagramas de Voronoi, en donde se codifica información sobre la proximidad e influencia en el plano a partir de un conjunto dado de puntos distribuidos por el. Este diagrama puede ser obtenido a partir de la triangulación de Delaunay gracias a la dualidad existente entre Voronoi-Delaunay, ya que la triangulación de Delaunay codifica la información referente a la vecindad de las regiones del diagrama de Vornoi. Sobre estos diagramas surgen de manera natural y casi inmediata unos modelos competitivos en donde los jugadores compiten posicionando puntos por el plano, buscando que la colocación de estos ejerza la mayor influencia sobre el área total del plano de manera que la de los jugadores rivales sea mínima. Esta competición es conocida como Juego de Voronoi. El estudio del Juego de Voronoi resulta un tema de investigación aún abierto en el campo de la Geometría Computacional, ya que conocer una estrategia ganadora sería de gran valor en diferentes ámbitos donde se pueden encontrar Juegos de Voronoi. Como se verá en el trabajo, el juego aquí presentado, conocido como la versión clásica del Juego de Voronoi, resulta por el momento intratable y no se conocen estrategias que garanticen la victoria, aunque si que existen una serie de variantes del juego que han sido estudiadas y presentan estrategias ganadoras así como estrategias de defensa para el rival, serán presentadas en el estudio del Estado del Arte que se encuentra en este trabajo. Todo este estudio teórico sienta la base para poder realizar una implementación del Juego de Voronoi en diferentes variantes, la variante clásica así como otra novedosa, aquí referida como versión dinámica, en la que los puntos son dotados de movimiento por el plano, un movimiento que es controlado por los jugadores que están participando en la partida.---ABSTRACT---This work is framed in the field of Computational Geometry, and deals with a structure that is known as the Voronoi Diagram, where information about the proximity and influence in the plane is encoded from a given set of points distributed by the plane. These diagrams can be obtained from the Delaunay Triangulation thanks to the duality between the two, as the triangulation encodes the neighborhood information of the regions that build the diagram. Competition models appear on these diagrams in a very natural and inmediate way, where the players compete against each other by positioning points in the plane, with the aim of maximizing the influence area of the region associated with their points. This is know as the Voronoi Game. The study of the Voronoi Game remains as an open research topic for the Computational Geometry and knowing a winning strategy for the game would be very valuable in the different situations where the game is found. As this work will present, the classic version of the game remains unstudied due to its complexity, and no strategies have been found, however, there are some game variants that are studied and count with strategies for the players. These will be presented in the State of the Art section of the work. All the theory about the diagrams and the game lays the foundations for an implementation of the game in different versions, a classic one, and a new one referred as dinamic, where the points move under the control of the player around the bidimensional plane.