Paralelizacija Delaunayeve triangulacije

ŽAUCER, SIMON (avtor), Ž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.

• Jezik: Slovenski jezik
• Ključne besede: triangulacija, deli in vladaj, Delaunay, paralelnost
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2019
• PID: 20.500.12556/RUL-110530
• COBISS.SI-ID: 1538347715
• Datum objave v RUL: 16.09.2019

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Parallelization of Delaunay triangulation

Izvleček

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.

• Ključne besede: triangulation, divide and conquer, Delaunay, paralelism