Parallel geometric algorithms for multi-core computers

A.L. Chow, Parallel algorithms for geometric problems, Ph.D. thesis, University of Illinois, Urbana–Champaign, IL, USA, 1980 Aggarwal, 1988, Parallel computational geometry, Algorithmica, 3, 293, 10.1007/BF01762120 Akl, 1993 CGAL Liu, 2005, A comparison of five implementations of 3D Delaunay tessellation, vol. 52, 439 Reinders, 2007 OpenMP Architecture Review Board, OpenMP Application Program Interface, Version 3.0, May 2008 J. Singler, B. Kosnik, The GNU libstdc++ parallel mode: software engineering considerations, in: Proc. 1st Intl. Worksh. Multicore Software Eng., 2008, pp. 15–22, doi:10.1145/1370082.1370089 J. Singler, P. Sanders, F. Putze, MCSTL: The multi-core standard template library, in: Proc. 13th Eur. Conf. Parallel and Distributed Comp., 2007, pp. 682–694 M. Hoffmann, L. Kettner, S. Pion, R. Wein, STL extensions for CGAL, in: CGAL Editorial Board (Ed.), CGAL Manual, 3.5 edition, 2009, http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/packages.html#Pkg:StlExtension N. Amenta, S. Choi, G. Rote, Incremental constructions con BRIO, in: Proc. 19th ACM Symp. Comp. Geom., 2003, pp. 211–219, doi:10.1145/777792.777824 C. Delage, Spatial sorting, in: CGAL Editorial Board (Ed.), CGAL Manual, 3.5 edition, 2009, http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/packages.html#Pkg:SpatialSorting Zomorodian, 2002, Fast software for box intersections, Int. J. Comp. Geom. Appl., 12, 143, 10.1142/S0218195902000785 L. Kettner, A. Meyer, A. Zomorodian, Intersecting sequences of dD iso-oriented boxes, in: CGAL Editorial Board (Ed.), CGAL Manual, 3.5 edition, 2009, http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/packages.html#Pkg:BoxIntersectionD Cignoni, 1993, Parallel 3D Delaunay triangulation, Comput. Graph. Forum, 12, 129, 10.1111/1467-8659.1230129 Cignoni, 1995, Evaluation of parallelization strategies for an incremental Delaunay triangulator in E3, Conc. Pract. Exp., 7, 61, 10.1002/cpe.4330070106 Lee, 2001, An improved parallel algorithm for Delaunay triangulation on distributed memory parallel computers, Parallel Process. Lett., 11, 341, 10.1142/S0129626401000634 Blelloch, 1999, Design and implementation of a practical parallel Delaunay algorithm, Algorithmica, 24, 243, 10.1007/PL00008262 Chen, 2006, Parallel divide-and-conquer scheme for 2D Delaunay triangulation, Conc. Comp. Pract. Exp., 18, 1595, 10.1002/cpe.1007 Puppo, 1994, Parallel terrain triangulation, Int. J. GIS, 8, 105 Lawson, 1977, Software for C1 surface interpolation, 161 N. Chrisochoides, F. Sukup, Task parallel implementation of the Bowyer–Watson algorithm, in: Proc. 5th Intl. Conf. Num. Grid Generation, 1996, pp. 773–782 T. Okusanya, J. Peraire, Parallel unstructured mesh generation, in: Proc. 5th Intl. Conf. Num. Grid Generation, 1996, pp. 719–729 Green, 1978, Computing Dirichlet tessellations in the plane, Comput. J., 21, 168, 10.1093/comjnl/21.2.168 Chrisochoides, 2003, Parallel Delaunay mesh generation kernel, Int. J. Numer. Methods Eng., 58, 161, 10.1002/nme.765 Okusanya, 1997, 3D parallel unstructured mesh generation, vol. 220, 109 Kohout, 2005, Parallel Delaunay triangulation in E2 and E3 for computers with shared memory, Parallel Comput., 31, 491, 10.1016/j.parco.2005.02.010 D.K. Blandford, G.E. Blelloch, C. Kadow, Engineering a compact parallel Delaunay algorithm in 3D, in: Proc. 22nd Symp. Comp. Geom., 2006, pp. 292–300, doi:10.1145/1137856.1137900 Clarkson, 1989, Applications of random sampling in computational geometry, II, Disc. Comp. Geom., 4, 387, 10.1007/BF02187740 J.R. Shewchuk, Tetrahedral mesh generation by Delaunay refinement, in: Proc. 14th ACM Symp. Comp. Geom., 1998, pp. 86–95 Antonopoulos, 2009, Algorithm, software, and hardware optimizations for Delaunay mesh generation on simultaneous multithreaded architectures, J. Parallel Distributed Comput., 69, 601, 10.1016/j.jpdc.2009.03.005 Antonopoulos, 2009, A multigrain Delaunay mesh generation method for multicore SMT-based architectures, J. Parallel Distributed Comput., 69, 589, 10.1016/j.jpdc.2009.03.009 Herlihy, 2008 M. Kulkarni, L.P. Chew, K. Pingali, Using transactions in Delaunay mesh generation, in: Proc. 1st Worksh. Transact. Memory Workloads, 2006 M.L. Scott, M.F. Spear, L. Dalessandro, V.J. Marathe, Delaunay triangulation with transactions and barriers, in: Proc. 10th Intl. Symp. Workload Characterization, 2007, pp. 107–113 Caşcaval, 2008, Software transactional memory: why is it only a research toy?, Commun. ACM, 51, 40, 10.1145/1400214.1400228 Boissonnat, 2002, Triangulations in CGAL, Comp. Geom. Theory Appl., 22, 5, 10.1016/S0925-7721(01)00054-2 J.-D. Boissonnat, O. Devillers, S. Hornus, Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension, in: Proc. 25th ACM Symp. Comp. Geom., 2009, pp. 208–216, doi:10.1145/1542362.1542403 Devillers, 2002, Walking in a triangulation, Int. J. Found. Comput. Sci., 13, 181, 10.1142/S0129054102001047 S. Pion, M. Teillaud, 3D triangulations, in: CGAL Editorial Board (Ed.), CGAL Manual, 3.5 edition, 2009, http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/packages.html#Pkg:Triangulation3