Geometrijski randomizirani algoritmi

master's thesis

• Author: Luka Milačić
• Mentor: Nina Kamčev (mentor)
• Committee member: Nina Kamčev (predsjednik povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Committee member: Rudi Mrazović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2025-01-14, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Ovaj rad istražuje ključne aspekte geometrijskih algoritama i struktura, s posebnim naglaskom na randomizaciju, dekompoziciju prostora i navigacijske strategije te koristi algoritama u stvarnom životu. U uvodnim dijelovima obrađuje se probleme konstrukcija konveksnih ljuski u ravnini i prostoru. Uz to definira se i koncept dualnosti s pomoću kojeg dobivamo "duale" prije opisanih problema. Za dane algoritme analiziramo njihovu očekivanu vremensku složenost. Nadalje, analiziraju se različite... More tehnike dekompozicije prostora uz korist randomizacije. Prvo definiramo Voronojieve dijagrame i Delaunayjeve triangulacije te dajemo randomizirani algoritam za njihovu konstrukciju koji je usko vezan s problemom konstrukcije konveksne ljuske u tri dimenzije. Uz to dajemo još jedan algoritam za slučaj triangulacije konveksnog poligona. Nakon toga dajemo randomizirane algoritme za konstrukcije trapezoidne dekompozicije i binarnih particija ravnine. Sve dekompozicije imaju široku primjenu u računalnoj geometriji s naglaskom na računalnoj grafici. U zadnjem poglavlju poseban fokus stavljen je na algoritme vezane uz Delaunayjeve triangulacije, gdje se razmatraju različite strategije usmjeravanja, uključujući razne jednostavne determinističke algoritme s naglaskom na pohlepnim algoritmima, te njihova proširenja kroz randomizaciju. Za sve algoritme mjerimo koliko su dobri definirajući im $c$-kompetitivnost. Ispituje se ograničenja determinističkih algoritama bez memorije i analiziraju njihovi negativni rezultati u specifičnim scenarijima. Na kraju poglavlja dajemo algoritam koji je $c$-kompetitivan. Završni dio sadrži kratku raspravu o algoritmima. Rad sintetizira teorijska saznanja i praktične primjene u području računalne geometrije, te pokazuje da su u nekim slučajevima jednostavniji algoritmi bolji za rješavanje određenih problema. Less

Abstract (english)

This paper explores key aspects of geometric algorithms and structures, with a special focus on randomization, space decomposition, and navigation strategies, as well as the practical applications of these algorithms in real life. In the introductory sections, the paper addresses the problems of constructing convex hulls in the plane and in space. The concept of duality is also defined, allowing us to obtain the ”duals” of the previously described problems. The expected time complexity of... More these algorithms is analyzed. Further, various space decomposition techniques utilizing randomization are explored. First, Voronoi diagrams and Delaunay triangulations are defined, and a randomized algorithm for their construction is presented, which is closely related to the problem of constructing a convex hull in three dimensions. Additionally, another algorithm for the triangulation of convex polygons is provided. The paper then presents randomized algorithms for the construction of trapezoidal decompositions and binary partitions of the plane. All these decompositions have broad applications in computational geometry, with an emphasis on computer graphics. The final chapter focuses on algorithms related to Delaunay triangulations, where different routing strategies are examined, including various simple deterministic algorithms with an emphasis on greedy algorithms, and their extensions through randomization. For all algorithms, their performance is evaluated by defining their c-competitiveness. The limitations of memoryless deterministic algorithms are examined, and their poor results in specific scenarios are analyzed. The chapter concludes with the presentation of the only c-competitive algorithm. The concluding section includes a brief discussion on the algorithms. This paper synthesizes theoretical insights and practical applications in the field of computational geometry, showing that in some cases, simpler algorithms are more effective for solving certain problems. Less

• Keywords: geometrijski algoritam; geometrijska struktura; randomizacija; dekompozicija prostora; navigacijske strategije; konveksne ljuske; Voronoi; Delauney
• Keywords (english): geometric algorithm; geometric structure; randomization; space decomposition; navigation strategies; convex hulls; Voronoi; Delauney
• Language: croatian
• URN:NBN: urn:nbn:hr:217:709479
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-12-21 17:12:08