Naslov Geometrijski randomizirani algoritmi Autor Luka Milačić Mentor Nina Kamčev (mentor)Član povjerenstva Nina Kamčev (predsjednik povjerenstva)Član povjerenstva Zvonimir Bujanović (član povjerenstva)Član povjerenstva Vjekoslav Kovač (član povjerenstva)Član povjerenstva Rudi Mrazović (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2025-01-14, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Sažetak 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
... Više 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 c Sakrij dio sažetka Sažetak (engleski) 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
... Više 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. Sakrij dio sažetka Ključne riječi
geometrijski algoritam
geometrijska struktura
randomizacija
dekompozicija prostora
navigacijske strategije
konveksne ljuske
Voronoi
Delauney
Ključne riječi (engleski)
geometric algorithm
geometric structure
randomization
space decomposition
navigation strategies
convex hulls
Voronoi
Delauney
Jezik hrvatski URN:NBN urn:nbn:hr:217:709479 Studijski program Naziv: Računarstvo i matematika Vrsta resursa Tekst Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2024-12-21 17:12:08
