Approximation Voronoi Diagram using Sampling in Two-Dimensional Space

As it is apparent, most of the time Voronoi diagram relates to using distance but due to the dependence of the number of the Voronoi cells to the number of the input points, the amount of used memory greatly depends on the number of the input points. In this paper, a new approach has been introduced for approximation Voronoi diagram. With this assumption that the numbers of Voronoi points are a lot, the points in dense regions have been merged and by considering one indicator for each region, the number of Voronoi cells decreases. In previous approaches, approximation Voronoi diagram was based on the number of the initial sites while in the proposed approach, the number of sites has decreased and substituted by the number of the indicators, and Voronoi diagram is just drawn for the indicator points. In fact, sampling and decline of the number of sites led to the decline of the number of the Voronoi cells, amount of memory, and decline of the number of calculations for specifying the boundaries. Initially, for sampling, an algorithm has been presented in which one indicator is chosen for each region. Then, Voronoi diagram is drown for all indicator points and eventually the experiments show although most of Voronoi cells have been deleted, the amount of density is completely shown

Keywords:

approximation Voronoi diagram , Voronoi diagram , approximative Voronoi cell , Voronoi diagram using sampling