{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:56Z","timestamp":1787337296681,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We present a theoretical framework for developing parallel guaranteed quality Delaunay mesh generation software that allows us to use commercial off\u2010the\u2010shelf sequential Delaunay meshers for two\u2010dimensional geometries. In this paper, we describe our approach for constructing uniform meshes, that is, the meshes in which all elements have approximately the same size. Our uniform distributed\u2010 and shared\u2010memory implementations are based on a simple (block) coarse\u2010grained mesh decomposition. Our method requires only local communication, which is bulk and structured as opposed to fine and unpredictable communication of the other existing practical parallel guaranteed quality mesh generation and refinement techniques. Our experimental data show that on a cluster of more than 100 workstations we can generate about 0.9 billion elements in less than 5 minutes in the absence of work\u2010load imbalances. Preliminary results for this paper were presented in [A. N. Chernikov and N. P. Chrisochoides, \u201cPractical and efficient point insertion scheduling method for parallel guaranteed quality Delaunay refinement,\u201d in Proceedings of the 18th Annual International Conference on Supercomputing, ACM Press, New York, 2004, pp. 48\u201357]. Our work in progress includes extending the presented approach, which can efficiently generate only uniform meshes, to nonuniform graded meshes.<\/jats:p>","DOI":"10.1137\/050625886","type":"journal-article","created":{"date-parts":[[2006,11,20]],"date-time":"2006-11-20T18:58:26Z","timestamp":1164049106000},"page":"1907-1926","source":"Crossref","is-referenced-by-count":33,"title":["Parallel Guaranteed Quality Delaunay Uniform Mesh Refinement"],"prefix":"10.1137","volume":"28","author":[{"given":"Andrey N.","family":"Chernikov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikos P.","family":"Chrisochoides","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,11,16]]},"reference":[{"key":"R1","unstructured":"C. D. Antonopoulos, X. Ding, A. N. Chernikov, F. Blagojevic, D. S. Nikolopoulos, and N. P. Chrisochoides,\n                      Multigrain parallel Delaunay mesh generation: Challenges and opportunities for multithreaded architectures\n                      , in Proceedings of the 19th Annual International Conference on Supercomputing, ACM Press, New York, 2005, pp. 367\u2013376."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.1264800"},{"key":"R3","unstructured":"G. Berti,\n                      Gral\u2014the grid algorithms library\n                      , in International Conference on Computational Science (3), P. M. A. Sloot, C. J. K. Tan, J. Dongarra, and A. G. Hoekstra, eds., Lecture Notes in Comput. Sci. 2331, Springer, Berlin, 2002, pp. 745\u2013754."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008262"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"R6","unstructured":"A. N. Chernikov and N. P. Chrisochoides,\n                      Practical and efficient point insertion scheduling method for parallel guaranteed quality Delaunay refinement\n                      , in Proceedings of the 18th Annual International Conference on Supercomputing, ACM Press, New York, 2004, pp. 48\u201357."},{"key":"R7","unstructured":"A. N. Chernikov and N. P. Chrisochoides,\n                      Parallel 2D graded guaranteed quality Delaunay mesh refinement\n                      , in Proceedings of the 14th International Meshing Roundtable, Springer, New York, 2005, pp. 505\u2013517."},{"key":"R8","unstructured":"L. P. Chew, N. Chrisochoides, and F. Sukup,\n                      Parallel constrained Delaunay meshing\n                      , in ASME\/ASCE\/SES Summer Meeting, Special Symposium on Trends in Unstructured Mesh Generation, Northwestern University, Evanston, IL, 1997, pp. 89\u201396."},{"key":"R9","unstructured":"L. P. Chew, N. Chrisochoides, K. Pingali, and S. Stodghil,\n                      Meshing Using Independent Sets\n                      , manuscript, 1999."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/nme.765"},{"key":"R11","unstructured":"N. P. Chrisochoides,\n                      A Survey of Parallel Mesh Generation Methods\n                      , Tech. Report BrownSC\u20102005\u201009, Brown University, 2005. Also appears as a chapter in Numerical Solution of Partial Differential Equations on Parallel Computers, M. Bruaset, P. Bjorstad, and A. Tveito, eds., Springer, New York, pp. 237\u2013259."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0956-0521(94)90014-0"},{"key":"R13","first-page":"793","volume":"7","author":"Delaunay B. N.","year":"1934","journal-title":"Otdelenie Mataematicheskii i Estestvennyka Nauk"},{"key":"R14","unstructured":"S. Dong, D. Lucor, and G. Em Karniadakis,\n                      Flow past a stationary and moving cylinder: DNS at $Re=10{,}000$\n                      , in 2004 Users Group Conference (DOD_UGC\u201904), IEEE, Williamsburg, VA, 2004, pp. 88\u201395."},{"key":"R15","unstructured":"H. Edelsbrunner and D. Guoy,\n                      Sink\u2010insertion for mesh improvement\n                      , in Proceedings of the 7th Annual Symposium on Computational Geometry, ACM Press, New York, 2001, pp. 115\u2013123."},{"key":"R16","unstructured":"P.\u2010L. George and H. Borouchaki,\n                      Delaunay Triangulation and Meshing. Application to Finite Elements\n                      , Herm\u00e8s, Paris, 1998."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00054-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)00085-O"},{"key":"R19","unstructured":"Y. Ito, A. M. Shih, A. K. Erukala, B. K. Soni, A. N. Chernikov, N. P. Chrisochoides, and K. Nakahashi,\n                      Generation of unstructured meshes in parallel using an advancing front method\n                      , in Proceedings of the 9th International Conference on Numerical Grid Generation in Computational Field Simulations, International Society of Grid Generation, 2005."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/3916.3988"},{"key":"R21","unstructured":"C. Kadow,\n                      Adaptive dynamic projection\u2010based partitioning for parallel Delaunay mesh generation algorithms\n                      , in SIAM Workshop on Combinatorial Scientific Computing, 2004."},{"key":"R22","unstructured":"C. Kadow and N. Walkington,\n                      Design of a projection\u2010based parallel Delaunay mesh generation and refinement algorithm\n                      , in Proceedings of the 4th Symposium on Trends in Unstructured Mesh Generation, 2003;"},{"key":"R22","unstructured":"http:\/\/www.andrew.cmu.edu\/user\/sowen\/usnccm03\/agenda.html."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1063\/1.881374"},{"key":"R24","unstructured":"A. Kot, A. N. Chernikov, and N. P. Chrisochoides,\n                      Out\u2010of\u2010core parallel Delaunay mesh generation\n                      , in Proceedings of the 17th IMACS World Congress Scientific Computation, Applied Mathematics and Simulation, Paper T1\u2010R\u201000\u20100710, Institute of Computational Mathematics and Mathematical Geophysics of the Russian Academy of Sciences, 2005."},{"key":"R25","unstructured":"V. Kumar, A. Grama, A. Gupta, and G. Karypis,\n                      Introduction to Parallel Computing: Design and Analysis of Parallel Algorithms\n                      , Benjamin\/Cummings, Redwood City, CA, 1994."},{"key":"R26","unstructured":"C. L. Lawson,\n                      Software for $C^1$ surface interpolation\n                      , in Mathematical Software, III, Academic Press, New York, 1977, pp. 161\u2013194."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/030602812"},{"key":"R28","unstructured":"R. L\u00f6hner and J. R. Cebral,\n                      Parallel advancing front grid generation\n                      , in Proceedings of the 8th International Meshing Roundtable, Sandia National Laboratories, Albuquerque, NM, 1999, pp. 67\u201374."},{"key":"R29","unstructured":"G. L. Miller, D. Talmor, S.\u2010H. Teng, and N. Walkington,\n                      A Delaunay based numerical method for three dimensions: Generation, formulation, and partition\n                      , in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1995, pp. 683\u2013692."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.009"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1021"},{"key":"R32","unstructured":"J. R. Shewchuk,\n                      Lecture notes on Delaunay mesh generation\n                      , http:\/\/www.cs.berkeley.edu\/\u223cjrs\/meshpapers\/delnotes.ps.gz (accessed November 2005)."},{"key":"R33","unstructured":"J. R. Shewchuk,\n                      Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator\n                      , in Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, eds., Lecture Notes in Comput. Sci. 1148, Springer, Berlin, 1996, pp. 203\u2013222."},{"key":"R34","unstructured":"J. R. Shewchuk,\n                      Delaunay Refinement Mesh Generation\n                      , Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA, 1997."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00047-5"},{"key":"R36","unstructured":"D. A. Spielman, S.\u2010H. Teng, and A. \u00dcng\u00f6r,\n                      Parallel Delaunay refinement: Algorithms and analyses\n                      , in Proceedings of the 11th International Meshing Roundtable, Sandia National Laboratories, Albuquerque, NM, 2001, pp. 205\u2013217."},{"key":"R37","unstructured":"J. R. Shewchuk,\n                      Time complexity of practical parallel Steiner point insertion algorithms\n                      , in Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, New York, 2004, pp. 267\u2013268."},{"key":"R38","unstructured":"S.\u2010H. Teng,\n                      Personal communication\n                      , 2004."},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.167"},{"key":"R40","unstructured":"R. Webster,\n                      Convexity\n                      , Oxford Science, New York, 1994, p. 200."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050625886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:55:21Z","timestamp":1787334921000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050625886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/050625886"],"URL":"https:\/\/doi.org\/10.1137\/050625886","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}