关键词: Voronoi图, MapReduce, Hadoop平台, 栅格生成算法

Abstract: For the efficiency of the raster generation of Voronoi diagram on a planar point set composed of massive points, after its embarrassingly parallel abstract, this paper proposes the raster generation of Voronoi diagram based on the Euclidean distance. The algorithm is designed with three MapReduce Jobs. During the first MapReduce Job, the rasters are classified by the attached code. During the second MapReduce Job, the new data are classified according to its corresponding line number. During the third MapReduce Job, the partial Voronoi diagrams are generated in parallel, and they maintain a global order, then the final Voronoi diagram is generated by connecting the partial Voronoi diagrams. The experiments on different sizes of datasets on the Hadoop platform demonstrate that the algorithm under MapReduce shows good performance on speedup and scaleup.

Key words: Voronoi diagram, MapReduce, Hadoop platform, raster generation algorithm