Finding the Voronoi diagram that most resembles a given subdivision of the plane algorithmically

Abstract

In this thesis we propose two algorithms that improve the similarity between a Voronoi cell and a simple polygon. The similarity measures used by these algorithms are the Hausdorff distance and the area of symmetric difference. The algorithm for the Hausdorff distance finds an optimal position in polynomial time. The running time of this algorithm depends on the number of sites, the number of vertices of the simple polygon, an arbitrarily chosen parameter ϵ > 0, and the number of neighbours of our site in several regions. These regions are regions where the set of neighbours of a site (when we change its location in this region) remain the same. The algorithm for the area of symmetric difference returns a position that is a factor (1 + ϵ') within the optimum in polynomial time for any ϵ' ∈ (0, 1). The running time of this algorithm depends on the same factors as the previous algorithm in addition to ϵ'. These algorithms can be used to improve the similarity between a Voronoi diagram and a tessellation iteratively, and we present an idea how to do so.