Interpolation error estimates in terms of geometric quality measures are established for harmonic coordinates on polytopes in two and three dimensions. First we derive interpolation error estimates over convex polygons that depend on the geometric quality of the triangles in the constrained Delaunay triangulation of the polygon. This characterization is sharp in the sense that families of polygons with poor quality triangles in their constrained Delaunay triangulations are shown to produce large error when interpolating a basic quadratic function. Non-convex polygons exhibit a similar limitation: large constrained Delaunay triangles caused by vertices approaching a non-adjacent edge also lead to large interpolation error. While this relationship is generalized to convex polyhedra in three dimensions, the possibility of sliver tetrahedra in the constrained Delaunay triangulation prevent the analogous estimate from sharply reflecting the actual interpolation error. Non-convex polyhedra are shown to be fundamentally different through an example of a family of polyhedra containing vertices which are arbitrarily close to non-adjacent faces yet the interpolation error remains bounded.
DOI : 10.1051/m2an/2015096
Mots-clés : Generalized barycentric coordinates, harmonic coordinates, polygonal finite elements, shape quality, interpolation error estimates
@article{M2AN_2016__50_3_651_0,
author = {Gillette, Andrew and Rand, Alexander},
title = {Interpolation error estimates for harmonic coordinates on polytopes},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {651--676},
publisher = {EDP-Sciences},
volume = {50},
number = {3},
year = {2016},
doi = {10.1051/m2an/2015096},
zbl = {1343.31004},
mrnumber = {3507268},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/m2an/2015096/}
}
TY - JOUR AU - Gillette, Andrew AU - Rand, Alexander TI - Interpolation error estimates for harmonic coordinates on polytopes JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2016 SP - 651 EP - 676 VL - 50 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/m2an/2015096/ DO - 10.1051/m2an/2015096 LA - en ID - M2AN_2016__50_3_651_0 ER -
%0 Journal Article %A Gillette, Andrew %A Rand, Alexander %T Interpolation error estimates for harmonic coordinates on polytopes %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2016 %P 651-676 %V 50 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/m2an/2015096/ %R 10.1051/m2an/2015096 %G en %F M2AN_2016__50_3_651_0
Gillette, Andrew; Rand, Alexander. Interpolation error estimates for harmonic coordinates on polytopes. ESAIM: Mathematical Modelling and Numerical Analysis , Special Issue – Polyhedral discretization for PDE, Tome 50 (2016) no. 3, pp. 651-676. doi : 10.1051/m2an/2015096. http://archive.numdam.org/articles/10.1051/m2an/2015096/
, Lagrange and average interpolation over 3D anisotropic elements. J. Comput. Appl. Math. 135 (2001) 91–109. | DOI | MR | Zbl
and , The maximum angle condition for mixed and nonconforming elements: application to the Stokes equations. SIAM J. Numer. Anal. 37 (2000) 18–36. | DOI | MR | Zbl
R.A. Adams, Sobolev Spaces. In vol. 140 of Pure and Applied Mathematics, 2nd edition. Academic Press, Oxford (2003). | Zbl
, and , A two-level method for mimetic finite difference discretizations of elliptic problems. Comput. Math. Appl. 70 (2015) 2674–2687. | DOI | MR | Zbl
T. Apel, Anisotropic Finite Elements: Local Estimates and Applications. Advances in Numerical Mathematics. Teubner, Stuttgart (1999). | MR | Zbl
and , On the angle condition in the finite element method. SIAM J. Numer. Anal. 13 (1976) 214–226. | DOI | MR | Zbl
I. Babuška, U. Banerjee and J. Osborn, Meshless and Generalized Finite Element Methods: A Survey of Some Major Results. In Meshfree Methods for Partial Differential Equations. Springer (2002) 1–20. | MR | Zbl
, , , , and , Basic principles of virtual element methods. Math. Models Methods Appl. Sci. 23 (2013) 199–214. | DOI | MR | Zbl
, and , Virtual elements for linear elasticity problems. SIAM J. Numer. Anal. 51 (2013) 794–812. | DOI | MR | Zbl
, , and , The hitchhiker’s guide to the virtual element method. Math. Models Methods Appl. Sci. 24 (2014) 1541–1573. | DOI | MR | Zbl
, Konvexe Bereiche gegebener konstanter Breite und kleinsten Inhalts. Math. Annal. 76 (1915) 504–513. | DOI | JFM | MR
P. Bochev and J. Hyman, Principles of Mimetic Discretizations of Differential Operators. In Compatible Spatial Discretizations. Springer (2006) 89–119. | MR | Zbl
and , Analysis of compatible discrete operator schemes for elliptic problems on polyhedral meshes. ESAIM: M2AN 48 (2014) 553–581. | DOI | Numdam | MR | Zbl
and , Analysis of compatible discrete operator schemes for the Stokes equations on polyhedral meshes. IMA J. Numer. Anal. 35 (2015) 1672–1697. | DOI | MR | Zbl
and , Estimation of linear functionals on Sobolev spaces with application to Fourier transforms and spline interpolation. SIAM J. Numer. Anal. 7 (1970) 112–124. | DOI | MR | Zbl
, and , On the equivalence of ball conditions for simplicial finite elements. Appl. Math. Lett. 22 (2009) 1210–1212. | DOI | MR | Zbl
S.C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods. Vol. 15 of Texts in Applied Mathematics. Springer, New York, third edition (2008). | MR | Zbl
, and , Mimetic scalar products of discrete differential forms. J. Comput. Phys. 257 (2014) 1228–1259. | DOI | MR | Zbl
, and , A family of mimetic finite difference methods on polygonal and polyhedral meshes. Math. Models Meth. Appl. Sci. 15 (2005) 1533–1551. | DOI | MR | Zbl
S. Cai and T.J. Tautges, One-to-one sweeping based on harmonic ST mappings of facet meshes and their cages. Engrg. Comput. (2014) 1–14.
, , and , Hourglass stabilization and the virtual element method. Int. J. Numer. Meth. Engng 1 (2014) 1–33. | Zbl
and , Optimal Delaunay triangulation. J. Comput. Math. 22 (2004) 299–308. | MR | Zbl
, , , and , Sliver exudation. J. ACM 47 (2000) 883–904. | DOI | MR | Zbl
, Constrained Delaunay triangulations. Algorithmica 4 (1989) 97–108. | DOI | MR | Zbl
P.G. Ciarlet, The Finite Element Method for Elliptic Problems. Vol. 40 of Classics in Applied Mathematics, 2nd edition. SIAM, Philadelphia, PA (2002). | MR | Zbl
, Boundary integral operators on Lipschitz domains: elementary results. SIAM J. Math. Anal. 19 (1988) 613–626. | DOI | MR | Zbl
and , On optimal interpolation triangle incidences. SIAM J. Sci. Stat. Comput. 10 (1989) 1063–1075. | DOI | MR | Zbl
and , The Bramble–Hilbert lemma for convex domains. SIAM J. Math. Anal. 35 (2004) 1203–1212. | DOI | MR | Zbl
, and , Hitchhikers guide to the fractional Sobolev spaces. Bull. Sci. Math. 136 (2012) 521–573. | DOI | MR | Zbl
, A proof of the trace theorem of Sobolev spaces on Lipschitz domains. Proc. Amer. Math. Soc. 124 (1996) 591–600. | DOI | MR | Zbl
, Error estimates for -d narrow finite elements. Math. Comput. 68 (1999) 187–199. | DOI | MR | Zbl
and , An experimental study of sliver exudation. Engrg. With Comput. 18 (2002) 229–240. | DOI
H. Edelsbrunner, X.-Y. Li, G. Miller, A. Stathopoulos, D. Talmor, S.-H. Teng, A. Üngör and N. Walkington. Smoothing and cleaning up slivers. In Proc. of ACM Symp. Theory Comput. (2000) 273–277. | MR | Zbl
A. Ern and J.-L. Guermond, Theory and Practice of Finite Elements. Vol. 159 of Applied Mathematical Sciences. Springer-Verlag, New York (2004). | MR | Zbl
, and , Polygonal finite elements. IEEE Trans. Magnetics 42 (2006) 675–678. | DOI
L.C. Evans, Partial Differential Equations. Vol. 19 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI (1998). | MR | Zbl
L.C. Evans and R.F. Gariepy. Measure theory and fine properties of functions. In vol. 5. CRC press (1991). | MR | Zbl
, Mean value coordinates. Comput. Aided Geom. Des. 20 (2003) 19–27. | DOI | MR | Zbl
, and , Gradient bounds for Wachspress coordinates on polytopes. SIAM J. Numer. Anal. 52 (2014) 515–532. | DOI | MR | Zbl
, and , Mean value coordinates in 3D. Comput. Aided Geom. Des. 22 (2005) 623–631. | DOI | MR | Zbl
, and , Error estimates for generalized barycentric coordinates. Adv. Comput. Math. 37 (2012) 417–439. | DOI | MR | Zbl
S. Guattery, G.L. Miller and N. Walkington, Estimating interpolation error: A combinatorial approach. In Proc. of 10th Symp. Discrete Algorithms (1999) 406–413. | MR | Zbl
, and , The maximum angle condition is not necessary for convergence of the finite element method. Numer. Math. 120 (2012) 79–88. | DOI | MR | Zbl
and , Maximum entropy coordinates for arbitrary polytopes. Comput. Graphics Forum 27 (2008) 1513–1520. | DOI
, Estimations d’erreur pour des éléments finis droits presque dégénérés. RAIRO Anal. Numér. 10 (1976) 43–61. | Numdam | MR | Zbl
, , , and , Harmonic coordinates for character articulation. ACM Trans. Graphics 26 (2007) 71. | DOI
, and , A general geometric construction of coordinates in a convex simplicial polytope. Comput. Aided Geom. Des. 24 (2007) 161–178. | DOI | MR | Zbl
, and , Mean value coordinates for closed triangular meshes. ACM Trans. Graphics 24 (2005) 561–566. | DOI
and , A Babuška-Aziz type proof of the circumradius condition. Jpn J. Ind. Appl. Math. 31 (2014) 193–210. | DOI | MR | Zbl
and , On the circumradius condition for piecewise linear triangular elements. Japan J. Ind. Appl. Math. 32 (2015) 65–76. | DOI | MR | Zbl
, On semiregular families of triangulations and linear interpolation. Appl. Math. 36 (1991) 223–232. | DOI | MR | Zbl
, On the maximum angle condition for linear tetrahedral elements. SIAM J. Numer. Anal. 29 (1992) 513–520. | DOI | MR | Zbl
T. Lambert, The Delaunay Triangulation Maximizes the Mean Inradius. In Proc. of Canadian Conf. Comput. Geom. Citeseer (1994) 201–206.
C.L. Lawson, Software for C1 Interpolation. In Mathematical Software III, edited by J.R. Rice (1977) 161–194. | MR | Zbl
, , and , Discrete Helmholtz–Hodge decomposition on polyhedral meshes using compatible discrete operators. J. Sci. Comput. 65 (2015) 34–53. | DOI | MR | Zbl
N.J. Lennes, Theorems on the simple finite polygon and polyhedron. Amer. J. Math. (1911) 37–62. | JFM | MR
G. Leoni, A First Course in Sobolev Spaces. Vol. 105 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI (2009). | MR | Zbl
and , Meshfree and particle methods and their applications. Appl. Mech. Rev. 55 (2002) 1–34. | DOI
, Generating well-shaped -dimensional Delaunay meshes. Theoret. Comput. Sci. 296 (2003) 145–165. | DOI | MR | Zbl
and , Poisson coordinates. IEEE Trans. Visualization Comput. Graphics 19 (2013) 344–352. | DOI
, and , Mimetic finite difference method. J. Comput. Phys. 257 (2014) 1163–1227. | DOI | MR | Zbl
, and , New perspectives on polygonal and polyhedral finite element methods. Math. Models Methods Appl. Sci. 24 (2014) 1665–1699. | DOI | MR | Zbl
, The trace of Sobolev-Slobodeckij spaces on Lipschitz domains. Manuscripta Math. 58 (1987) 47–65. | DOI | MR | Zbl
S. Martin, P. Kaufmann, M. Botsch, M. Wicke and M. Gross, Polyhedral finite elements using harmonic basis functions. In Proc. of Symp. Geom. Proc. (2008) 1521–1529.
G.L. Miller, D. Talmor, S.-H. Teng and N. Walkington, On the radius-edge condition in the control volume method. SIAM J. Numer. Anal. (1999) 1690–1708. | MR | Zbl
, and , Weak Galerkin finite element methods on polytopal meshes. Int. J. Numer. Anal. Model. 12 (2015) 31–53. | MR | Zbl
, Minimal roughness property of the Delaunay triangulation: A shorter approach. Comput. Aided Geom. Des. 9 (1992) 491–494. | DOI | MR | Zbl
, On a generalization of Schönhardt’s polyhedron. Combin. Comput. Geom. 52 (2003) 510–516. | Zbl
A. Rand, Delaunay Refinement Algorithms for Numerical Methods. Ph.D. thesis, Carnegie Mellon University (2009). | MR
, Average interpolation under the maximum angle condition. SIAM J. Numer. Anal. 50 (2012) 2538–2559. | DOI | MR | Zbl
, and , Interpolation error estimates for mean value coordinates. Adv. Comput. Math. 39 (2013) 327–347. | DOI | MR | Zbl
, Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Des. 7 (1990) 489–497. | DOI | MR | Zbl
, Long and thin triangles can be good for linear interpolation. SIAM J. Numer. Anal. 29 (1992) 257–270. | DOI | MR | Zbl
and , Minimum energy triangulations for elliptic problems. Comput. Methods Appl. Mech. Engrg. 84 (1990) 257–274. | DOI | MR | Zbl
, Über die zerlegung von dreieckspolyedern in tetraeder. Math. Annal. 98 (1928) 309–312. | DOI | JFM | MR
, Uniform error estimates for certain narrow Lagrange finite elements. Math. Comput. 63 (1994) 105–119. | DOI | MR | Zbl
, General-dimensional constrained Delaunay and constrained regular triangulations, I: Combinatorial properties. Discrete Comput. Geom. 39 (2008) 580–637. | DOI | MR | Zbl
, Locally equiangular triangulations. Comput. J. 21 (1978) 243–245. | DOI | MR
, A vector identity for the Dirichlet tessellation. Math. Proc. Cambridge Philos. Soc. 87 (1980) 151–155. | DOI | MR | Zbl
, Construction of polygonal interpolants: a maximum entropy approach. Int. J. Numer. Methods Eng. 61 (2004) 2159–2181. | DOI | MR | Zbl
and , Overview and construction of meshfree basis functions: From moving least squares to entropy approximants. Int. J. Numer. Methods Eng. 70 (2007) 181–205. | DOI | MR | Zbl
, , and , Natural neighbour Galerkin methods. Int. J. Numer. Meth. Engng 50 (2001) 1–27. | DOI | MR | Zbl
J.L. Synge, The Hypercircle in Mathematical Physics. Cambridge University Press, Cambridge (1957). | MR | Zbl
and , Application of polygonal finite elements in linear elasticity. Int. J. Comput. Methods 3 (2006) 503–520. | DOI | MR | Zbl
, A note on polynomial approximation in Sobolev spaces. Math. Model. Numer. Anal. 33 (1999) 715–719. | DOI | Numdam | MR | Zbl
E. Wachspress, A Rational Finite Element Basis. Vol. 114 of Mathematics in Science and Engineering. Academic Press, New York (1975). | MR | Zbl
and , A weak Galerkin finite element method for second-order elliptic problems. J. Comput. Appl. Math. 241 (2013) 103–115. | DOI | MR | Zbl
and , A weak Galerkin mixed finite element method for second order elliptic problems. Math. Comput. 83 (2014) 2101–2126. | DOI | MR | Zbl
, Barycentric coordinates for convex polytopes. Adv. Comput. Math. 6 (1996) 97–108. | DOI | MR | Zbl
, , and , Barycentric coordinates for convex sets. Adv. Comput. Math. 27 (2007) 319–338. | DOI | MR | Zbl
, and , A finite element method on convex polyhedra. Comput. Graphics Forum 26 (2007) 355–364. | DOI
O. Zienkiewicz and R. Taylor, The Finite Element Method, 5th edition. Butterworth-Heinemann, London (2000). | MR | Zbl
Cité par Sources :
