A new parallel algorithm for constructing Voronoi tessellations from distributed input data. (English) Zbl 1360.65076

Summary: We present a new parallel algorithm for generating consistent Voronoi diagrams from distributed input data for the purposes of simulation and visualization. The algorithm functions by building upon any serial Voronoi tessellation algorithm. The output of such a serial tessellator is used to determine the connectivity of the distributed domains without any assumptions about how points are distributed across those domains, and then in turn to build the portion of the global tessellation local to each domain using information from that domains neighbors. The result is a generalized methodology for adding distributed capabilities to serial tessellation packages. Results from several two-dimensional tests are presented, including strong and weak scaling of its current implementation.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y05 Parallel numerical computation


Polytope; TetGen
Full Text: DOI


[1] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S. N., Spatial tessellations: concepts and applications of Voronoi diagrams, (2000), John Wiley and Sons Chichester, West Sussex, England · Zbl 0946.68144
[2] Rycroft, C., Chaos, 19, 041111, (2009)
[3] Shewchuk, J., Appl. Comput. Geom., 1148, 203-222, (1996)
[4] H. Si, Tetgen (Version 1.4.3). Available at http://tetgen.org (accessed 28.01.12), 2011.
[5] A. Sydorchuk, Boost.Polygon Voronoi Library (Version 1.0). Available at http://www.boost.org (accessed 25.03.13), 2010-2012.
[6] Fortune, S., Algorithmica, 2, 153-174, (1987)
[7] Jacobsen, D.; Gunzburger, M.; Ringler, T.; Burkardt, J.; Peterson, J., Geosci. Model Dev. Discuss., 6, 1427-1466, (2013)
[8] Wang, J.; Cui, C.; Rui, Y.; Cheng, L.; Pu, Y.; Wu, W.; Yuan, Z., Concurrency Comput.: Pract. Exp., (2013)
[9] Loubere, R.; Maire, P.-H.; Shashkov, M.; Breil, J.; Galera, S., J. Comput. Phys., 229, 4724-4761, (2010)
[10] Springel, V., Mon. Not. R. Astron. Soc., (2009), in press
[11] R. Merland, B. Levy, G. Caumon, IAMG 2011 Conference Proceedings, 2011.
[12] Cole, R.; Goodrich, M.; Dunlaing, C., Algorithmica, 16, 569-617, (1996)
[13] D. Blandford, G. Blelloch, C. Kadow, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, 2006, p. 292.
[14] Blelloch, G.; Hardwick, J.; Miller, G.; Talmor, D., Algorithmica, 24, 243-269, (1999)
[15] Chrisochoides, N.; Nave, D., Internat. J. Numer. Methods Engrg., 58, 161-176, (2003)
[16] Lee, S.; Park, C.-I.; Park, C.-M., Parallel Process. Lett., 11, 341, (2001)
[17] Owen, J. M., SPHERIC Newsl., 13, (2011)
[18] J.M. Owen, Applications of the Voronoi Tessellation for Mesh-Free Methods, Multimat [Presentation], 2011.
[19] Ledoux, H.; Gold, C. M., Int. J. Geogr. Inf. Sci., 22, 547-574, (2008)
[20] H. Ledoux, Voronoi Diagrams in Science and Engineering 2007 Conference Proceedings, 2007.
[21] Koradi, R.; Billeter, M.; Guntert, P., Comput. Phys. Comm., 124, 139-147, (2000)
[22] Pearce, O.; Gamblin, T.; de Supinski, B.; Schulz, M.; Amato, N., Int. Conf. Supercomput., 185-194, (2012)
[23] Du, Q.; Faber, V.; Gunzburger, M., SIAM Rev., 41, 4, 637-676, (1999)
[24] Du, Q.; Wang, D.; Zhu, L., SIAM J. Numer. Anal., 47, 2, 1421-1444, (2009)
[25] D. Sieger, P. Alliez, M. Botsch, Proceedings of the 19th International Meshing Roundtable, 2010, pp. 335-350.
[26] Yan, D.-M.; Levy, B.; Sun, F.; Wang, W., Comput. Graph. Forum, 28, 5, 1445-1454, (2009)
[27] Lloyd, S., IEEE Trans. Inform. Theory, 28, 129-137, (1982)
[28] J. Johnson, J.M. Owen, D. Starinshak, Polytope (Version 0.5.17). Available at https://bitbucket.org/jjphatt/polytope, 2013.
[29] D.-M. Yan, W. Wang, B. Levy, Y. Liu, GMP 2010 Conference Proceedings, 2010.
[30] B. Gehrels, B. Lalande, M. Loskot, A. Wulkiewicz, Boost.Geometry Library (Version 1.0), Available at http://www.boost.org (accessed 07.06.12).
[31] Garimella, R.; Shashkov, M., Eng. Comput., 20, 265-272, (2004)
[32] Taylor, G.; Green, A., Proc. R. Soc. A, 158, 499-521, (1937)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.