Algorithms for convex hull in three-dimensional space

Otoczka wypukła stanowi jeden z najpowszechniejszych obiektów w geometrii obliczeniowej. Zewzględu na jej rozliczne zastosowania opracowano wiele algorytmów zapewniającychminimalizację złożoności obliczeniowej problemu. W części przypadków istnieje możliwośćuogólnienia na n-wymiarową przestrzeń euklidesową. W pracy opracowano dwa algorytmywyznaczające otoczkę w przestrzeni trójwymiarowej wykorzystując publikacje naukowepoświęcone zagadnieniu konstruowania tego typu obiektów. Ich poprawność została zweryfikowanaprzy pomocy implementacji programów w języku Java, które umożliwiają również interaktywnąwizualizację etapów wyznaczania otoczki wypukłej zbioru punktów.The convex hull is one of the most common constructs in computational geometry. Due to itsnumerous uses, many algorithms have been developed to minimize the computational complexity ofthe problem. In some cases there is the possibility of generalization in the n-dimensional Euclideanspace. In this thesis, two methods have been elaborated to define the convex hull in threedimensionalspace using scientific publications devoted to this subject. The correctness ofapproaches has been verified with the implementation of Java programs, which also enable aninteractive step-by-step visualization of convex hull construction