A parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping
文献类型：SCI/SSCI论文
| 作者 | Wang J. C. ; Cui C. ; Rui Y. K. ; Cheng L. ; Pu Y. X. ; Wu W. Z. ; Yuan Z. Y. |
| 发表日期 | 2014 |
| 关键词 | Voronoi diagrams parallel algorithm adaptive grouping geographical information system computational geometry |
| 英文摘要 | This paper presents a parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub-Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable.After constructing the sub-Voronoi diagrams, we extracted the boundary points of the four sides of each sub-group and used to construct boundary site Voronoi diagrams. Finally, the sub-Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright (c) 2013 John Wiley & Sons, Ltd. |
| 出处 | Concurrency and Computation-Practice & Experience |
| 卷 | 26 |
| 期 | 2 |
| 页 | 434-446 |
| 收录类别 | SCI |
| 语种 | 英语 |
| ISSN号 | 1532-0626 |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/29565]  |
| 专题 | 地理科学与资源研究所_历年回溯文献 |
| 推荐引用方式 GB/T 7714 | Wang J. C.,Cui C.,Rui Y. K.,et al. A parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping. 2014. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。