Triangulaciones y diagramas de Voronoi

Abstract

La Geometría Discreta Computacional trata de las construcciones geométricas que pueden realizarse a partir de un número finito de puntos. En el casoplano, las construcciones básicas son, junto con el cálculo del cierre convexo de un conjunto finito de puntos, las triangulaciones de polígonos y los diagramas de Voronoi, que son en cierto modo construcciones duales. Este trabajo estudia los resultados fundamentales de ambas construcciones,haciendo especial énfasis en los aspectos algorítmicos. Este tema tiene aplicaciones prácticas en muchas áreas, entre las que se encuentran la cartografía, el diseño asistido por ordenador, la visión artificial o la robótica.