carrier image

How Efficient are Delaunay Refined Meshes? An Empirical Study

Simpson, Bruce

Proceedings, 15th International Meshing Roundtable, Springer-Verlag, pp.215-238, September 17-20 2006


15th International Meshing Roundtable
Birmingham, Alabama, U.S.A.
September 17-20, 2006

School of Computer Science
University of Waterloo, Waterloo,
Ontario, Canada, N2L 3G1

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, fpl(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 fpl(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.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article