Algoritmos geométricos sobre la esfera

Resumen

En este trabajo de fin de grado se realiza un estudio del cierre convexo, la
triangulación de Delaunay, y el diagrama de Voronoi de puntos en posición general
situados sobre la superficie de una esfera. Además se proponen algoritmos geométricos
eficientes para el cómputo de las estructuras mencionadas, fundamentales en el ámbito
de la Geometría Computacional, sobre la esfera.
Para la realización de este estudio, se hace uso del cierre convexo tridimensional, que,
al igual que en el plano, se encuentra estrechamente relacionado con el objeto del
trabajo, y de operaciones esenciales de la Geometría Computacional como son el
volumen signado de cuatro puntos o el vector normal de una superficie.
Adicionalmente se han implementado los algoritmos propuestos en SageMath, un
sistema de software matemático libre basado en Python, con ayuda de la herramienta
Qhull para el cálculo del cierre convexo tridimensional. La implementación se ha
realizado para puntos aleatorios uniformemente distribuidos sobre la esfera unidad y
sus resultados se muestran en las secciones correspondientes del trabajo.
Para concluir, se muestran imágenes del globo terráqueo aproximado como una esfera,
aplicando los algoritmos implementados a puntos que representan capitales del
mundo.---ABSTRACT---This project studies the convex hull, Delaunay triangulation and Voronoi diagram of
sets of points in general position located on the surface of a sphere. Moreover, it
proposes eficient geometric algorithms to compute said structures, essential in the
scope of Computational Geometry, on the unit sphere.
For this study, the three-dimensional convex hull is used, which, as in the case of the
plane, is closely related to the object of this work. Likewise, essential operations of
Computational Geometry are used, such as the signed volume of four points or the
normal vector of a surface.
Additionally, the algorithms proposed have been implemented in SageMath, an
open-source mathematical software system based on Python, with the help of the
Qhull tool for the computation of a three-dimensional convex hull. The
implementation was performed for uniformly distributed random points on the unit
sphere, and its results are shown in the corresponding sections of the work.
To conclude, images of planet Earth considered as a sphere are shown, applying the
implemented algorithms to points that represent capitals of the world.