Summary
We develop a theoretical framework for constructing guaranteed quality Delaunay meshes in parallel for general two-dimensional geometries. This paper presents a new approach for constructing graded meshes, i.e., meshes with element size controlled by a user-defined criterion. The sequential Delaunay refinement algorithms are based on inserting points at the circumcenters of triangles of poor quality or unacceptable size. We call two points Delaunay-independent if they can be inserted concurrently without destroying the conformity and Delaunay properties of the mesh. The contribution of this paper is three-fold. First, we present a number of local conditions of point Delaunay-independence, which do not rely on any global mesh metrics. Our sufficient conditions of point Delaunay-independence allow to select points for concurrent insertion in such a way that the standard sequential guaranteed quality Delaunay refinement procedures can be applied in parallel to attain the required element quality constraints. Second, we prove that a quadtree, constructed in a specific way, can be used to guide the parallel refinement, so that the points, simultaneously inserted in multiple leaves, are Delaunay-independent. Third, by experimental comparison with the well-known guaranteed quality sequential meshing software, we show that our method does not lead to overrefinement, while matching its quality and allowing for code re-use.
This work was supported by NSF grants: EIA-9972853, EIA-0203974, and ACI-0312980
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. E. Blelloch, J. Hardwick, G. L. Miller, and D. Talmor. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24:243–269, 1999.
G. E. Blelloch, G. L. Miller, and D. Talmor. Developing a practical projectionbased parallel Delaunay algorithm. In 12th Annual Symposium on Computational Geometry, pages 186–195, 1996.
A. Bowyer. Computing Dirichlet tesselations. Computer Journal, 24:162–166, 1981.
A. N. Chernikov and N. P. Chrisochoides. Parallel guaranteed quality planar Delaunay mesh generation by concurrent point insertion. In 14th Annual Fall Workshop on Computational Geometry, pages 55–56. MIT, Nov. 2004.
A. N. Chernikov and N. P. Chrisochoides. Practical and efficient point insertion scheduling method for parallel guaranteed quality Delaunay refinement. In Proceedings of the 18th annual international conference on Supercomputing, pages 48–57. ACM Press, 2004.
N. P. Chrisochoides. A survey of parallel mesh generation methods. Technical Report BrownSC-2005-09, Brown University, 2005. To appear in Numerical Solution of Partial Differential Equations on Parallel Computers (eds. Are Magnus Bruaset, Petter Bjorstad, Aslak Tveito).
S. Dong, D. Lucor, and G. E. Karniadakis. Flow past a stationary and moving cylinder: DNS at Re=10,000. In 2004 Users Group Conference (DOD UGC’04), pages 88–95, 2004.
H. Edelsbrunner and D. Guoy. Sink-insertion for mesh improvement. In Proceedings of the Seventeenth Annual Symposium on Computational Geometry, pages 115–123. ACM Press, 2001.
P.-L. George and H. Borouchaki. Delaunay Triangulation and Meshing. Application to Finite Elements. HERMES, 1998.
C. Kadow. Adaptive dynamic projection-based partitioning for parallel Delaunay mesh generation algorithms. In SIAM Workshop on Combinatorial Scientific Computing, Feb. 2004.
C. Kadow. Parallel Delaunay Refinement Mesh Generation. PhD thesis, Carnegie Mellon University, 2004.
C. Kadow and N. Walkington. Design of a projection-based parallel Delaunay mesh generation and refinement algorithm. In Fourth Symposium on Trends in Unstructured Mesh Generation, July 2003. http://www.andrew.cmu.edu/user/sowen/usnccm03/agenda.html.
G. Karnriadakis and S. Orszag. Nodes, modes, and flow codes. Physics Today, 46:34–42, 1993.
L. Linardakis and N. Chrisochoides. Parallel domain decoupling Delaunay method. SIAM Journal on Scientific Computing, in print, accepted Nov. 2004.
G. L. Miller, D. Talmor, S.-H. Teng, and N. Walkington. A Delaunay based numerical method for three dimensions: Generation, formulation, and partition. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pages 683–692. ACM Press, May 1995.
D. Nave, N. Chrisochoides, and L. P. Chew. Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains. Computational Geometry: Theory and Applications, 28:191–215, 2004.
J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of Algorithms, 18(3):548–585, 1995. Parallel 2D Graded Guaranteed Quality Delaunay Mesh Refinement 517
J. R. Shewchuk. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Proceedings of the First workshop on Applied Computational Geometry, pages 123–133, Philadelphia, PA, 1996.
J. R. Shewchuk. Delaunay Refinement Mesh Generation. PhD thesis, Carnegie Mellon University, 1997.
D. A. Spielman, S.-H. Teng, and A. Üngör. Parallel Delaunay refinement: Algorithms and analyses. In Proceedings of the Eleventh International Meshing Roundtable, pages 205–217, 2001.
D. A. Spielman, S.-H. Teng, and A. Üngör. Time complexity of practical parallel Steiner point insertion algorithms. In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 267–268. ACM Press, 2004.
R. A. Walters. Coastal ocean models: Two useful finite element methods. Recent Developments in Physical Oceanographic Modelling: Part II, 25:775–793, 2005.
D. F. Watson. Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Computer Journal, 24:167–172, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chernikov, A.N., Chrisochoides, N.P. (2005). Parallel 2D Graded Guaranteed Quality Delaunay Mesh Refinement. In: Hanks, B.W. (eds) Proceedings of the 14th International Meshing Roundtable. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-29090-7_30
Download citation
DOI: https://doi.org/10.1007/3-540-29090-7_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25137-8
Online ISBN: 978-3-540-29090-2
eBook Packages: EngineeringEngineering (R0)