Parallel geometric algorithms for multi-core computers

ABSTRACT

Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations for mesh generation algorithms or simply computing Delaunay triangulations. We show experimental results for these algorithms in 3D, using our implementations based on the Computational Geometry Algorithms Library (CGAL, http://www.cgal.org/). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.

REFERENCES

• 1: Alok Aggarwal, Bernard Chazelle, Leonidas J. Guibas, Colm Ó'Dúnlaing, and Chee-Keng Yap. Parallel computational geometry. Algorithmica, 3(1--4):293--327, 1988.
• 2: Selim G. Akl , Kelly A. Lyons, Parallel computational geometry, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 3: Nina Amenta , Sunghee Choi , Günter Rote, Incremental constructions con BRIO, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777824]
• 4: Vicente H. F. Batista, David L. Millman, Sylvain Pion, and Johannes Singler. Parallel geometric algorithms for multi-core computers. Research Report 6749, INRIA, 2008. http://hal.inria.fr/inria-00343804.
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: Daniel K. Blandford , Guy E. Blelloch , Clemens Kadow, Engineering a compact parallel delaunay algorithm in 3D, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137900]
• 7: Guy E. Blelloch, Jonathan C. Hardwick, Gary L. Miller, and Dafna Talmor. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3):243--269, 1999.
• 8: Jean-Daniel Boissonnat , Olivier Devillers , Samuel Hornus, Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542403]
• 9: Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. Comp. Geom. Theory & Appl., 22:5--19, 2002.
• 10: Adrian Bowyer. Computing Dirichlet tesselations. Comput. J., 24(2):162--166, 1981.
• 11: Anita Liu Chow. Parallel algorithms for geometric problems. PhD thesis, University of Illinois, Urbana-Champaign, IL, USA, 1980.
• 12: Paolo Cignoni, Domenico Laforenza, Claudio Montani, Raffaele Perego, and Roberto Scopigno. Evaluation of parallelization strategies for an incremental Delaunay triangulator in E³. Conc. Pract. and Exp., 7(1):61--80, 1995.
• 13: Paolo Cignoni, Claudio Montani, Raffaele Perego, and Roberto Scopigno. Parallel 3D Delaunay triangulation. Comput. Graph. Forum, 12(3):129--142, 1993.
• 14: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 15: Christophe Delage. Spatial sorting. In CGAL Editorial Board, editor, CGAL Manual. 3.4 edition, 2008.
• 16: Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Int. J. Found. Comput. Sci., 13(2):181--199, 2002.
• 17: Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Ron Wein. STL extensions for CGAL. In CGAL Editorial Board, editor, CGAL Manual. 3.4 edition, 2008.
• 18: Lutz Kettner, Andreas Meyer, and Afra Zomorodian. Intersecting sequences of dD iso-oriented boxes. In CGAL Editorial Board, editor, CGAL Manual. 3.4 edition, 2008.
• 19: Josef Kohout , Ivana Kolingerová , Jiří Žára, Parallel Delaunay triangulation in E² and E³ for computers with shared memory, Parallel Computing, v.31 n.5, p.491-522, May 2005 [doi>10.1016/j.parco.2005.02.010]
• 20: Sangyoon Lee, Chan-Ik Park, and Chan-Mo Park. An improved parallel algorithm for Delaunay triangulation on distributed memory parallel computers. Parallel Processing Letters, 11(2/3):341--352, 2001.
• 21: Yuanxin Liu and Jack Snoeyink. A comparison of five implementations of 3D Delaunay tessellation. In Jacob E. Goodman, J'anos Pach, and Emo Welzl, editors, Combinatorial and Computational Geometry, volume 52 of MSRI Publications, pages 439--458. Cambridge University Press, 2005.
• 22: Sylvain Pion and Monique Teillaud. 3D triangulations. In CGAL Editorial Board, editor, CGAL Manual. 3.4 edition, 2008.
• 23: James Reinders, Intel threading building blocks, O'Reilly & Associates, Inc., Sebastopol, CA, 2007
• 24: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 25: Johannes Singler , Benjamin Konsik, The GNU libstdc++ parallel mode: software engineering considerations, Proceedings of the 1st international workshop on Multicore software engineering, May 11-11, 2008, Leipzig, Germany [doi>10.1145/1370082.1370089]
• 26: Johannes Singler, Peter Sanders, and Felix Putze. MCSTL: The multi-core standard template library. In Proc. 13th Eur. Conf. Parallel and Distributed Comp., pages 682--694, 2007.
• 27: Hans Tangelder and Andreas Fabri. dD spatial searching. In CGAL Editorial Board, editor, CGAL Manual. 3.4 edition, 2008.
• 28: David F. Watson. Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Comput. J., 24(2):167--172, 1981.
• 29: Afra Zomorodian and Herbert Edelsbrunner. Fast software for box intersections. Int. J. Comp. Geometry Appl., 12(1-2):143--172, 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Experimentation, Performance

Keywords:
box intersection, cgal, compact container, d-dimension, delaunay triangulations, geometric algorithms, kd-trees, multi-core, parallel algorithms, spatial sort