Massive Data Delaunay Triangulation Based on Grid Partition Method

A Delaunay triangulation method is brought forward oriented massive data, which based on the grid partition method. It divides the data set into some grid tiles, constructs Delaunay triangulation for each grid tile by divide-and-conquer algorithm based on self-adapt gird partition, and store some unaffected triangles, then merges adjacent Delaunay triangulations to whole or whole-like Delaunay triangulation. This method requires low computer hardware, fits for parallel processing, can process Delaunay triangulation of massive data.