Paralelní konstrukce konvexní obálky

Abstract

Tato závěrečná práce je věnována problému konvexní obálky množiny bodů a algoritmům pro její výpočet. Hlavním úkolem této práce bylo navrhnout novou verzi algoritmu Quickhull, která využívá "crawlery" ve fázi předzpracování, a porovnat její výkonnost k výkonnosti algoritmu Quickhull, algoritmu Concurrent Hull, a jiným implementacím řešičů problému konvexní obálky množiny bodů. Pro splnění tohoto zadání jsme analyzovali problém konvexní obálky množiny bodů a algoritmy navržené pro její výpočet. Následně jsme navrhli a implementovali algoritmus Quickhull, algoritmus Concurrent Hull, a nový algoritmus Quickhull with Crawlers pro výpočet na CPU pomocí OpenMP API, a pro výpočet na GPU pomocí CUDA API a knihovny Thrust. Pro zhodnocení kvality našich implementací jsme změřili jejich výkonnost na vstupech vygenerovaných generátory vstupních bodů, které jsme navrhli a implementovali. Následně jsme porovnali výkonnost našich implementací mezi sebou, a s již existující knihovnou Qhull. V závěru této práce jsme navrhli možnosti pro budoucí vývoj našich implementací, a nápady pro další výzkum v oboru problému konvexní obálky množiny bodů.

This thesis is dedicated to the field of the convex hull problem and algorithms for computing the convex hull of points. The main task of this thesis was to design a new version of the Quickhull algorithm that utilizes "crawlers" during the preprocessing phase and compare its performance to the performance of the Quickhull algorithm, the Concurrent Hull algorithm, and other implementations of solvers of the convex hull problem. To accomplish this goal, we studied the convex hull problem and the state-of-the-art algorithms designed for solving the convex hull problem. Subsequently, we designed and implemented the Quickhull algorithm, the Concurrent Hull algorithm, and the new Quickhull with Crawlers algorithm for computation on the CPU using the OpenMP API, and for computation on the GPU using the CUDA API and the Thrust library. To evaluate the quality of our implementations, we measured their performance on datasets outputted by generators of input points we designed and implemented. We compared the performance of our implementations with each other, as well as with the already existing Qhull library. In conclusion to this thesis, we proposed ideas for further development of our implementations as well as ideas for future research in the field of the convex hull problem.