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.

Description

Title: Algoritmos geométricos sobre la esfera
Author/s:
  • Quintero Rey, Germán Francisco
Contributor/s:
  • Abellanas Oar, Manuel
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2016
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
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

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.

More information

Item ID: 42903
DC Identifier: http://oa.upm.es/42903/
OAI Identifier: oai:oa.upm.es:42903
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 18 Jul 2016 08:25
Last Modified: 27 Oct 2016 07:52
  • 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