IGSNRR OpenIR
Adaptive parallel Delaunay triangulation construction with dynamic pruned binary tree model in Cloud
Lin, Jiaxiang1,2; Chen, Riqing1; Wu, Liping1; Shu, Zhaogang1; Yang, Changcai1
2017-12-25
Source PublicationCONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
ISSN1532-0626
Volume29Issue:24Pages:10
Corresponding AuthorChen, Riqing(riqing.chen@fafu.edu.cn)
AbstractThe paper illustrates a parallel and distributed scheme for computing a planar Delaunay triangulation using a divide-and-conquer strategy in Cloud environment, which combines the incremental insertion algorithm and the divide-and-conquer method. The proposed hybrid algorithm for Delaunay triangulation construction is easy to be parallelized due to the dynamic pruned characteristic of the binary tree model used. Moreover, the Cloud platform decreases the communication overhead and improves data locality by making use of a data partitioning and integrating scheme offered by the map-reduce architecture. The implementation of the parallel and distributed version of the algorithm relied on a robust data structure called quad-edge, which implies the geometric relationship among the edges and vertexes adjacent. More importantly, the data are serialized easily and transmitted efficiently between different Cloud nodes; the algorithm is executed conveniently on PC clusters. We tested the parallel version of the algorithm on GeoKSCloud, a geographical knowledge service Cloud developed by our research team. Experimental results show that the proposed hybrid algorithm is efficient and competitive; it can be easily migrated and deployed in distributed and parallel computing environment, such as grid and Cloud. The parallel implementation of the hybrid algorithm has a good speed-up, while data communication is the crucial factor for the efficiency of the parallel version. Overall, the parallel version outperforms both the sequential divide-and-conquer algorithm and the sequential incremental insertion algorithm.
KeywordDelaunay TIN distributed and parallel cloud services divide and conquer incremental insertion
DOI10.1002/cpe.4157
WOS KeywordINCREMENTAL CONSTRUCTION ; VORONOI DIAGRAMS ; CONQUER SCHEME ; ALGORITHM ; COMPUTATION
Indexed BySCI
Language英语
Funding ProjectNational Natural Science Foundation of China[41401458] ; National Natural Science Foundation of China[61501120] ; Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University[2017LSDMIS01] ; Key Program of Science and Technology of Fujian Province[2015H0015] ; Natural Science Foundation of Fujian Province of China[2014J05045] ; Natural Science Foundation of Fujian Province of China[2016J05148] ; Natural Science Foundation of Fujian Province of China[2016J01753] ; Science and Technology Foundation of The Education Department of Fujian Province of China[JA12375] ; Youth Foundation of Fujian Agriculture and Forestry University[k13xjj05a]
Funding OrganizationNational Natural Science Foundation of China ; Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University ; Key Program of Science and Technology of Fujian Province ; Natural Science Foundation of Fujian Province of China ; Science and Technology Foundation of The Education Department of Fujian Province of China ; Youth Foundation of Fujian Agriculture and Forestry University
WOS Research AreaComputer Science
WOS SubjectComputer Science, Software Engineering ; Computer Science, Theory & Methods
WOS IDWOS:000416017600003
PublisherWILEY
Citation statistics
Document Type期刊论文
Identifierhttp://ir.igsnrr.ac.cn/handle/311030/56783
Collection中国科学院地理科学与资源研究所
Corresponding AuthorChen, Riqing
Affiliation1.Fujian Agr & Forestry Univ, Coll Comp & Informat Sci, Fuzhou 350002, Fujian, Peoples R China
2.Chinese Acad Sci, Inst Geog Sci & Nat Resources Res, Beijing 100101, Peoples R China
Recommended Citation
GB/T 7714
Lin, Jiaxiang,Chen, Riqing,Wu, Liping,et al. Adaptive parallel Delaunay triangulation construction with dynamic pruned binary tree model in Cloud[J]. CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE,2017,29(24):10.
APA Lin, Jiaxiang,Chen, Riqing,Wu, Liping,Shu, Zhaogang,&Yang, Changcai.(2017).Adaptive parallel Delaunay triangulation construction with dynamic pruned binary tree model in Cloud.CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE,29(24),10.
MLA Lin, Jiaxiang,et al."Adaptive parallel Delaunay triangulation construction with dynamic pruned binary tree model in Cloud".CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 29.24(2017):10.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Lin, Jiaxiang]'s Articles
[Chen, Riqing]'s Articles
[Wu, Liping]'s Articles
Baidu academic
Similar articles in Baidu academic
[Lin, Jiaxiang]'s Articles
[Chen, Riqing]'s Articles
[Wu, Liping]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Lin, Jiaxiang]'s Articles
[Chen, Riqing]'s Articles
[Wu, Liping]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.