Implementación de un Método Paralelo de Triangulación Delaunay Euclídeo

Abstract

En el presente trabajo se muestran los avances en la implementación de un método paralelizable para triangulación Delaunay de un conjunto de puntos. El método se basa en la subdivisión recursiva del dominio mediante un plano/recta y la identificación de todos los elementos Delaunay que intersectan dicho plano/recta. El método se ha implementado tanto con modelos de memoria compartida como con modelos de memoria local y se presentan los análisis de tiempo y complejidad algorítmica de cada uno, comparativamente con respecto al mismo método no paralelizado y con respecto al método tradicional de inserción de nodos en orden aleatorio.