Approximation of the order-k voronoi diagram

Abstract

This paper presents an algorithm for constructing a generalized discrete order-k Voronoi diagram on the grid with variable step, based on the idea of recursive partitioning space. The algorithm uses a partitioning tree (2d-tree) as a data structure, also known as quadtree and octree for 2 and 3 dimensional spaces. The algorithm recursively refines the boundaries of Voronoi cells (bisectors), using only local properties at each point of the construction area. As a result, the calculations are concentrated in the area of the cell boundaries (the depth of the 2d-tree is larger in the region of the cell boundaries), and a significant performance gain is achieved compared with the naive algorithm (brute force). The algorithm allows to generalize the shape of sites, the metric used, the order of the diagram and the number of measurements.