Dualidad Triangulación de Delaunay - Diagrama de Voronoi mediante polaridad 3D

Abstract

La geometría computacional es una rama de la matemática en la que se afrontan problemas geométricos y cómo resolverlos de la forma más eficiente posible. El interés se enfoca en el diseño y estudio de algoritmos que optimicen el tiempo de computación de dichos problemas. Las técnicas producidas en la geometría computacional son utilizadas en ramas como la robótica, los sistemas de información geográfica, ingeniería asistida por computadora, etc. En el presente trabajo nos vamos a centrar en dos estructuras muy recurrentes en Geometría Computacional, la triangulación de Delaunay y el diagrama de Voronoi en 2 dimensiones. En los primeros capítulos definiremos dichas estructuras y los conceptos necesarios para entender la relación que se definirá entre los espacios bidimensional y tridimensional. Dichas relaciones se fundamentarán en la dualidad y polaridad respecto al paraboloide x 2 + y 2 = z. De esta forma podremos definir una transformación bidireccional entre nuestras estructuras sobre puntos en el espacio bidimensional y el estudio de dichos puntos elevados sobre el paraboloide. Gracias a esta aplicación podemos dar una alternativa al cálculo habitual de la triangulación de Delaunay y el diagrama de Voronoi, de manera que, a partir de dichas relaciones, podemos diseñar e implementar algoritmos que nos permitan dar una expresión gráfica al problema. En cada capítulo posterior al de “Conceptos Previos’’ nos centraremos en una de las relaciones, abordándolas a nivel teórico y mostrando la naturaleza gráfica de dicha dualidad, además de explicar el pseudocódigo utilizado para la transformación de ambos problemas relacionados. En los últimos capítulos nos centraremos en la generalización de nuestros problemas a la métrica elíptica, así como a superficies distintas al paraboloide. Para finalizar, evaluaremos los resultados y conclusiones obtenidas derivadas del estudio de las relaciones entre problemas bidimensionales y tridimensionales, así como de las oportunidades que este tipo de relaciones pueden ofrecer a otros problemas.---ABSTRACT---Computational geometry is a branch of mathematics that studies geometric problems and how to solve them in the most efficient way possible. The interest focuses on the design and study of algorithms that optimize the computation time of these problems. The techniques produced in computational geometry are used in branches such as robotics, geographic information systems, computer-aided engineering, etc. In this paper we are going to focus on two very important structures for Computational Geometry, Delaunay triangulation and the Voronoi diagram in 2 dimensions. In the first chapters we will define these structures and the concepts necessary to understand the relationship that will be defined between the two-dimensional and three-dimensional spaces. These relationships will be based on duality and polarity with respect to the paraboloid x 2 + y 2 = z. In this way we can define a bidirectional transformation between our structures about points in twodimensional space and the study of said high points on the paraboloid. Thanks to this application we can give an alternative to the usual calculation of Delaunay's triangulation and the Voronoi diagram, so that, from these relationships, we can design and implement algorithms that allow us to give a graphic expression of the problem. In each chapter after "Prior Concepts" we will focus on one of the relationships, studying them at a theoretical level and showing the graphic nature of said duality, in addition to explaining the pseudocode used for the transformation of both related problems. In the last chapters we will focus on the generalization of our problems to the elliptical metric, as well as to surfaces other than the paraboloid. Finally, we will evaluate the results obtained and the conclusions obtained derived from the study of the relations between two-dimensional and threedimensional problems, as well as the opportunities that this type of relations can offer to other problems.