Change search
ReferencesLink to record
Permanent link

Direct link
A parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping
KTH, School of Architecture and the Built Environment (ABE), Urban Planning and Environment, Geodesy and Geoinformatics.
Show others and affiliations
2014 (English)In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 26, no 2, 434-446 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2014. Vol. 26, no 2, 434-446 p.
Keyword [en]
Voronoi diagrams, parallel algorithm, adaptive grouping, geographical information system, computational geometry
National Category
Geosciences, Multidisciplinary
URN: urn:nbn:se:kth:diva-141288DOI: 10.1002/cpe.3005ISI: 000329764200007ScopusID: 2-s2.0-84892532426OAI: diva2:696178

QC 20140213

Available from: 2014-02-13 Created: 2014-02-13 Last updated: 2014-02-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Rui, Yikang
By organisation
Geodesy and Geoinformatics
In the same journal
Concurrency and Computation
Geosciences, Multidisciplinary

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 72 hits
ReferencesLink to record
Permanent link

Direct link