Abstract
Given a data function, f(x, y), defined for (x, y) in a domain,D and an error measure for approximating f on D, we can call a piecewise linear function, f pl(x, y), acceptable if its error measure is less than or equal to a given error tolerance. Adaptive Delaunay Refinement (ADR) is one approach to generating a mesh for D that can be used to create an acceptable f pl(x, y). A measure of the efficiency of methods for generating a mesh, M, for piecewise approximation is the size of M. In this paper, we present empirical evidence that ADR generated meshes can be twice a large as necessary for producing acceptable interpolants for harmonic functions. The error measure used in this study is the maximum of the triangle average L2 errors in M. This observation is based on demonstrating a comparison mesh generating using maximal efficiency mesh theory as reviewed in the paper. There are two different approaches to point placement commonly used in ADR, edge based refinement and circumcenter based refinement. Our study indicates that there is no significant difference in the efficiency of the meshes generated by these two approaches.
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
1. A. Adler. On the bisection method for triangles. Mathematics of Computation, 40:571–574, 1983. similarity classes.
2. T. J. Baker. Triangulations, mesh generation and point placement strategies. In D. Caughey, editor, Computing the Future, pages 61–75. John Wiley, 1994.
3. R. E. Bank. PLTMG: A Software Package for Solving Elliptic Partial Differential Equations, Users' Guide 8.0. SIAM, Philadelphia, 1998.
4. R. E. Bank and A. H. Sherman. The use of adaptive grid refinement for badly behaved elliptic partial Differential equations. In R. Vichnevetsky and R. S. Stepleman, editors, Advances in Computer Methods for Partial Differential Equations-III, pages 33–39. IMACS, 1979.
5. R. E. Bank and A. Weiser. Some a posteriori error estimators for elliptic partial differential equations. Math Comp, 44(170):283–301, 1985.
6. M. Berzins. A solution-based triangular and tetrahedral mesh quality indicator. SIAM J. Sci. Stat. Comput., 19:2051–2060, 1998.
7. H. Borouchaki and P. L. George. Aspects of 2-d delaunay mesh generation. International Journal for Numerical Methods in Engineering, 40:1957–1975, 1997.
8. L. Paul Chew. Guaranteed-quality mesh generation for curved surfaces. In Proc. 9th Annual Comp. Geometry. ACM Press, 1993. QA448.D38S87x.
9. E. F. D'Azevedo. Optimal triangular mesh generation by coordinate transformation. SIAM J. Sci. Stat. Comput., 12:755–786, 1991.
10. E. F. D'Azevedo. On adaptive mesh generation in two-dimensions. In S Owen, editor, Proceedings: 8th International Meshing Round Table. Sandia National Laboratories, 1999.
11. E. F. D'Azevedo and R. B. Simpson. On optimal interpolation triangle incidences. SIAM J. Sci. Stat. Comput., 10:1063–1075, 1989.
12. W. H. Frey. Selective refinement: A new strategy for automatic node placement in graded triangular meshes. International Journal for Numerical Methods in Engineering, 24:2183–2200, 1987.
13. P. L. George and H. Borouchaki. Delaunay Triangulation and Meshing. Hermes, 1998.
14. D. J. Mavriplis. Adaptive mesh generation for viscous flows using Delaunay triangulation. Journal of Computational Physics, 90:271–291, 1990.
15. E. Nadler. Piecewise Linear Approximation on Triangles of a Planar Region. PhD thesis, Brown University, 1985. order Number DA8519885.
16. J. Peraire, M. Vahdati, K. Morgan, and O. C. Zienkiewicz. Adaptive remeshing for compressible flow computations. Journal of Computational Physics, 72, 1987.
17. S. Rippa. Long and thin triangles can be good for linear interpolation. SIAM J. Numer. Analysis, 9:257–270, 1992.
18. M.-C. Rivara. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. International Journal for Numerical Methods in Engineering, 20:745–756, 1984.
19. M. C. Rivara. New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations. Int. J. Num. Methods, 40:3313–3324, 1997.
20. M. C. Rivara and N. Hitschfeld. LEPP-Delaunay algorithm: a robust tool for producing size-optimal quality triangulations. In Proc. of the 8th Int. Meshing Roundtable, pages 205–220, October 1999.
21. M.-C. Rivara and M. Palma. New LEPP-Algorithms for quality polygon and volume triangulation: Implementation issues and proctical behavior. In Trends in Unstructured Mesh Generation, volume AMD-Vol. 220, pages 1–8. American Society of Meshanical Engineers, 1997. The Joint ASME/ASCE/SES Summer Meeting, Evanston, Illinois, USA, July 1997.
22. J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensi onal mesh generation. J of Algorithms, 18:548–585, 1995.
23. G. Sewell. A finite element program with automatic user-controlled mesh grading. In R. Vichnevetsky and R. S. Stepleman, editors, Advances in Computer Methods for Partial Differential Equations- III, pages 8–10. IMACS, 1979.
24. J. R. Shewchuck. What is a good linear element? interpolation, conditioning, and quality measures. In S. Owen, editor, Proceedings: 11th International Meshing Round Table. Sandia National Laboratories, 2002.
25. J. R. Shewchuk. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In ACM, editor, First Workshop on Applied Computational Geometry, pages 124–133. (Philadelphia, Pennsylvania), 1996.
26. R. B. Simpson. Anisotropic mesh transformations and optimal error control. Applied Num. Math., 14:183–198, 1994.
27. I. S. Sokolnikoff. Tensor Analysis. Theory and Applications to Geometry and echanics of Continua. Wiley, 2nd edition, 1964.
28. G. Strang and G. J. Fix. An Analysis of the Finite Element Method. Prentice Hall, 1973.
29. N. Sukumar. Voronoi cell finite difference method for the diffusion operator on arbitrary unstructured grids. International Journal for Numerical Methods in Engineering, 57:1–34, 2003. Laplacian.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer
About this paper
Cite this paper
Simpson, B. (2006). How Efficient are Delaunay Refined Meshes? An Empirical Study. In: Pébay, P.P. (eds) Proceedings of the 15th International Meshing Roundtable. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-34958-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-34958-7_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34957-0
Online ISBN: 978-3-540-34958-7
eBook Packages: EngineeringEngineering (R0)