| Popis: |
V diplomskem delu predstavimo geometrijsko strukturo imenovano Voronoijev diagram. Najprej bomo pogledali definicijo in splošne lastnosti Voronojevega diagrama. Nato bomo pregledovali različne variacije na osnovno idejo in njihove praktične uporabe ter za njih predstavili nekatere lastnosti. Drugi del diplomskega dela se bo osredotočil na tako imenovane Voronoijeve diagrame najbolj oddaljenih točk, kjer bomo poleg njihovih posebnosti tudi pogledali algoritem za naključnostno prirastno konstrukcijo (textit{angl.:} randomized incremental construction) diagrama in zatem še analizirali njegovo pričakovano časovno zahtevnost. Zadnji del je namenjen spoznanju posplošene oblike Voronoijevih diagramov, imenovano Abstraktni Voronoijevi diagrami. Tudi tukaj bomo pogledali idejo algoritma za naključno prirastno konstrukcijo in ocenili njeno pričakovano časovno in prostorsko zahtevnost. In the thesis we present a geometric structure called Voronoi diagram. At first we will take a look at the definition and some basic properties of the Voronoi diagram. After that we will see different variations on the basic idea, their practical usage, and we will also present some of their properties. The second part will focus on the so-called Farthest-Point Voronoi diagrams. Beside their specificities, we will also see a RIC (randomized incremental construction) algorithm to calculate the diagram and analyze its expected running time. The last part is meant to show a generalized version of Voronoi diagrams, called Abstract Voronoi diagrams. Here we will also see the idea for a RIC algorithm and evaluate its expected running time and space. |
