Adaptive parallel Delaunay triangulation construction with dynamic pruned binary tree model in Cloud

摘要

The paper illustrates a parallel and distributed scheme for computing a planar Delaunay triangulationrnusing a divide-and-conquer strategy in Cloud environment, which combines the incrementalrninsertion algorithm and the divide-and-conquer method. The proposed hybrid algorithmrnfor Delaunay triangulation construction is easy to be parallelized due to the dynamic prunedrncharacteristic of the binary treemodel used.Moreover, the Cloud platform decreases the communicationrnoverhead and improves data locality by making use of a data partitioning and integratingrnscheme offered by the map-reduce architecture. The implementation of the parallel and distributedrnversion of the algorithm relied on a robust data structure called quad-edge,which impliesrnthe geometric relationship among the edges and vertexes adjacent. More importantly, the datarnare serialized easily and transmitted efficiently between different Cloud nodes; the algorithmrnis executed conveniently on PC clusters. We tested the parallel version of the algorithm onrnGeoKSCloud, a geographical knowledge service Cloud developed by our research team. Experimentalrnresults show that the proposed hybrid algorithm is efficient and competitive; it can berneasily migrated and deployed in distributed and parallel computing environment, such as gridrnand Cloud. The parallel implementation of the hybrid algorithm has a good speed-up, while datarncommunication is the crucial factor for the efficiency of the parallel version. Overall, the parallelrnversion outperforms both the sequential divide-and-conquer algorithm and the sequentialrnincremental insertion algorithm.