| Popis: |
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. |
