Paralelizacija Delaunayeve triangulacije

ŽAUCER, SIMON (author), Žabkar, Jure (mentor)

Diplomska naloga je narejena z namenom pohitritve Delaunayeve triangulacije, ki jo uporablja podjetje KobiLabs d.o.o. V prvem delu diplomske naloge smo na kratko predstavili različne tipe Delaunayeve triangulacije in izpostavili prednosti triangulacije tipa deli in vladaj. V nadaljevanju smo triangulacijo tipa deli in vladaj paralelizirali z več nitnostjo. Ugotovili smo, da algoritem triangulacije tipa deli in vladaj brez paralelizacije doseže primerljivo hitrost s knjižnico Triangle, vendar pa je mogoče s paralelizacijo doseči precejšnjo pohitritev.

• Language: Slovenian
• Keywords: triangulacija, deli in vladaj, Delaunay, paralelnost
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2019
• PID: 20.500.12556/RUL-110530
• COBISS.SI-ID: 1538347715
• Publication date in RUL: 16.09.2019

Secondary language

• Language: English
• Title: Parallelization of Delaunay triangulation

Abstract

Thesis is made with purpose of speeding up Delaunay triangulation, which is used by the company KobiLabs d.o.o. In first section of the thesis we briefly introduce different types of Delaunay triangulation and showed benefits of using divide and conquer triangulation. After we paralelised divide and conquer triangulation using multithreading. From results it is apparent that our divide and conquer triangulation is comparable to Triangle in terms of speed, but we managed to gain a large speedup due to paralelisation.

• Keywords: triangulation, divide and conquer, Delaunay, paralelism