Error Estimates for the Interpolation and Approximation of Gradients and Vector Fields on Protected Delaunay Meshes in ℝ \mathbb{R} d
David M. Williams, Mathijs Wintraecken · 2025
Read Error Estimates for the Interpolation and Approximation of Gradients and Vector Fields on Protected Delaunay Meshes in ℝ \mathbb{R} d by David M. Williams, Mathijs Wintraecken (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18987.txt.
Introduction
David Williams and Mathijs Wintraecken derive in 2025 explicit error estimates for estimating gradients and vector fields on protected Delaunay meshes. Meshes of triangles or tetrahedra underpin simulation, and workers often need slopes, not just values, at mesh points. Rigorous bounds for high-order fits in more than two dimensions were scarce.
The pair bound the error for piecewise polynomial fits of any order. Accuracy turns partly on the thinnest cell in the mesh, a quantity that protected meshes let builders control exactly. The analysis extends from gradients to any smooth vector field. Explicit bounds tell simulation engineers how fine and how plump their meshes must be before trusting computed flows.
Catalog record
| CREATOR | David M. Williams, Mathijs Wintraecken |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18987
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Error Estimates for the Interpolation and Approximation of Gradients and Vector Fields on Protected Delaunay Meshes in ℝ \mathbb{R} d David M. Williams, Mathijs Wintraecken Abstract One frequently needs to interpolate or approximate gradients on simplicial meshes. Unfortunately, there are very few explicit mathematical results governing the interpolation or approximation of vector-valued functions on Delaunay meshes in more than two dimensions. Most of the existing results are tailored towards interpolation with piecewise linear polynomials. In contrast, interpolation with piecewise high-order polynomials is not well understood. In particular, the results in this area are sometimes difficult to immediately interpret, or to specialize to the Delaunay setting. In order to address this issue, we derive explicit error estimates for high-order, piecewise polynomial gradient interpolation and approximation on protected Delaunay meshes. In addition, we generalize our analysis beyond gradients, and obtain error estimates for sufficiently-smooth vector fields. Throughout the paper, we show that the quality of interpolation and approximation often depends (in part) on the minimum thickness of simplices in the mesh. Fortunately, the minimum thickness can be precisely controlled on protected Delaunay meshes in ℝ d \mathbb{R}^{d} . keywords protected Delaunay, interpolation, high-order, higher-dimensions, error estimates 1 Introduction The primary purpose of this article is to motivate the construction of protected Delaunay meshes in higher dimensions, d>2 . In order to avoid confusion, we will refer to traditional Delaunay meshes which satisfy an empty-sphere criterion as standard Delaunay meshes. In contrast, a protected Delaunay mesh satisfies a modified empty-sphere criterion, where the sphere of each simplex is augmented by a spherical-buffer region. The original sphere with radius R , is effectively replaced by an augmented sphere with radius R+r . Here, we insist that r\geq\delta , for some \delta>0 . In this context, the quantity \delta is called the protection . Broadly speaking, our goal is to make \delta as large as possible, as this has two positive ramifications: (i) it increases the minimum size of slivers in the Delaunay mesh, and (ii) it reduces the sensitivity of the Delaunay mesh to the locations of its points Boissonnat et al. (2014) . Here, we define a sliver element, as an element which has a very small ratio of its minimum altitude to its maximum edge length. In this work, we are primarily interested in slivers, as we can directly reduce the errors of gradient (or vector-field) interpolation and approximation by increasing the minimum size of slivers. Of course, in a standard Delaunay mesh without protection, the thickness of a sliver can become arbitrarily close to zero, (for d>2 ). Fortunately, in cases where the protection is non-zero, we obtain fatter simplices whose thickness is bounded away from zero. This fact was established in the pioneering work of Boissonnat, Dyer, and Ghosh Boissonnat et al. (2013) . More precisely, they showed that slivers naturally arise from pathological configurations of d+2 vertices which are nearly co-spherical. These pathological configurations can be avoided by carefully perturbing the mesh points to facilitate the construction of a protected Delaunay mesh. A procedure for perturbing the points has been proposed in Boissonnat et al. (2014) . In addition, a detailed summary of protected Delaunay meshes appears in Boissonnat et al. (2018) . The relationship between standard Delaunay meshes and protected Delaunay meshes is illustrated in Figure 1 . Figure 1: A diagram of the relationship between standard Delaunay meshes and protected Delaunay meshes. The protection parameter is denoted by \delta . Evidently, only a strict subset of all standard Delaunay meshes can be classified as protected Delaunay meshes. Now, having established the concept of a protected Delaunay mesh, let us expand our discussion in order to present some broader perspectives on the entire field of Delaunay meshing. Generally speaking, standard Delaunay meshes have a very good reputation among scientists and engineers. This positive reputation has been documented in many places, including the excellent textbooks of Cheng, Dey, and Shewchuk Cheng et al. (2013) , and Borouchaki and George Borouchaki and George (2017) . However, in our opinion, the reputation of these meshes is mostly based on their optimality properties in \mathbb{R}^{2} . Unfortunately, there is a weaker justification for using standard Delaunay meshes in higher dimensions. In particular, Delaunay triangulations of nets (well-spaced point sets) still contain slivers in dimensions higher than 2 , while in 2D the quality of simplices in a standard Delaunay triangulation of a net is lower bounded (as mentioned previously). In the next section, we will provide a short review of important properties of standard Delaunay meshes, and identify areas for potential improvement. 1.1 Background: Properties of Standard Delaunay Meshes 1.1.1 The Two-Dimensional Case There are many important results which govern the shape and quality of triangles in standard Delaunay meshes in \mathbb{R}^{2} . For example, Sibson Sibson (1978) proved that a standard Delaunay triangulation of a point set S is guaranteed to maximize the minimum-interior angle of its triangles, relative to any other triangulation of the same points. In addition, Musin Musin (1993) ; Musin (1997) proved that the standard Delaunay triangulation of S minimizes the average circumradius of triangles in the triangulation. In a similar fashion, Lambert Lambert (1994) proved that the standard Delaunay triangulation of S maximizes the average inradius. Furthermore, Musin Musin (1995) proved that the standard Delaunay triangulation minimizes the harmonic index functional, where the functional is the sum over each triangle of the squared edge lengths divided by the triangle area. In more recent work, Musin Musin (2010) conjectured that the mean radius functional and the D functional are minimized on standard Delaunay triangulations. Here, the mean radius functional is an area-weighted sum of the squared circumradii, and the D functional is an area-weighted sum of the squared distance between the barycenter and circumcenter of each triangle. Following this work, Edelsbrunner et al. Edelsbrunner et al. (2017) proved that the mean radius functional is minimized on standard Delaunay triangulations. In addition, they showed that the Voronoi functional is maximized on the same triangulations. For the sake of brevity, the precise formulation of the Voronoi functional will not be described here; the interested reader is encouraged to consult Akopyan (2009) for details. Furthermore, a detailed summary of the optimality properties of standard Delaunay triangulations appears in Sierra’s thesis Sierra (2021) . Most of the results above, govern the shape-regularity of triangles in a standard Delaunay triangulation. Essentially, these results ensure that the triangles resemble equilateral triangles, as much as possible. One may also obtain results which directly predict the interpolation or approximation accuracy of a standard Delaunay triangulation. In particular, Rippa Rippa (1990) and Powar Powar (1992) proved that the piecewise linear interpolations of H^{1} functions have minimal roughness on a standard Delaunay triangulation. Here, the roughness of the linear interpolation is defined as the integral of the squared magnitude of the gradient. This quantity naturally arises when a classical finite element method is applied to elliptic problems in \mathbb{R}^{2} . In Rippa and Schiff (1990) , Rippa and Schiff leveraged the roughness result of Rippa (1990) , and proved that standard Delaunay triangulations minimize the solution error for simple elliptic problems. Thereafter, Shewchuk Shewchuk (2002) performed an exhaustive study of piecewise linear interpolation on generic triangular and