In the thesis we first describe the definition of a Voronoi diagram and several properties of Voronoi diagrams in the plane. We also define triangulations of the plane and the concept of a Delaunay triangulation, and present the connection between Voronoi diagrams and Delaunay triangulations. We then present three different algorithms for constructing a Voronoi diagram in the plane, and provide a more detailed description of Fortune’s algorithm which is an example of a sweep line algorithm. Sweep line algorithms are especially widespread in computational geometry and are used for solving various problems in Euclidean space. We selected Fortune’s algorithm for constructing Voronoi diagrams, and implemented it in the Java programming language. The performance of our implementation of the algorithm was checked on several randomly generated datasets and on a dataset of geographic coordinates of public charging stations for electric cars in Slovenia.
|
