A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons

Computing efficiency and the type of generator are a limitation and barely sustain the construction of Voronoi diagrams based on polyline/polygons. Thus, a new decomposition and combination algorithm for polyline/polygons is proposed in this paper, the main procedure transforms polyline/polygons into discrete feature points. According to cross connection characteristics, vicinity feature points pairs are constructed, whose cross parts of Voronoi diagrams can be substitute for the equal distance boundaries of polyline/polygons. Based on the area differences in iterative discrete computational sub-Voronoi regions, before and after, the generator is alternative in the iterative procedure that making sub-Voronoi region being gradually adjusted to the required precision. From empirical results and analysis, it can be concluded is that the time complexity of the proposed algorithm is O(n²) at high precision. Lastly, generated effect of polyline/polygon Voronoi diagram in the case of ample data using this algorithm is revealed.