Algoritmos geométricos sobre la esfera

Quintero Rey, Germán Francisco (2016). Algoritmos geométricos sobre la esfera. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: Algoritmos geométricos sobre la esfera
Autor/es:
  • Quintero Rey, Germán Francisco
Director/es:
  • Abellanas Oar, Manuel
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Junio 2016
Materias:
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

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.

Más información

ID de Registro: 42903
Identificador DC: http://oa.upm.es/42903/
Identificador OAI: oai:oa.upm.es:42903
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 18 Jul 2016 08:25
Ultima Modificación: 27 Oct 2016 07:52
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM