Juego de Voronoi dinámico

Donís Ebri, Pablo (2020). Juego de Voronoi dinámico. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Juego de Voronoi dinámico
Author/s:
  • Donís Ebri, Pablo
Contributor/s:
  • Abellanas Oar, Manuel
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2020
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
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

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.

More information

Item ID: 63152
DC Identifier: http://oa.upm.es/63152/
OAI Identifier: oai:oa.upm.es:63152
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 22 Jul 2020 17:24
Last Modified: 22 Jul 2020 17:24
  • 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