Xeometría Computacional

Abstract

[GL] O obxectivo deste traballo será tratar tres temas da xeometría, tales como a triangulación de polígonos, a envolvente convexa e os diagramas de Voronoi. En cada un deles aportaremos os conceptos máis básicos, partiremos dunha serie de resultados teóricos, e postularemos un problema ao que daremos resposta mediante a xeometría computacional. En todos eles tentaremos detallar a explicación aos algoritmos que abordan dito problema, e nalgúns elaboraremos e engadiremos o código de ditos algoritmos implementado na linguaxe de programación Python.

[EN] The goal of this work will be to deal with three topics of geometry, such as triangulation of polygons, convex hull and Voronoi diagrams. In each of them we will present the most basic concepts, we will start with some theoretical results, and we will postulate a problem which will be answered by means of computational geometry. In all of them we will try to detail the explanation of the algorithms that solve the problem, and in some of them we will develop and add the code of these algorithms implemented in the Python programming language.