Interpolation error estimates for harmonic coordinates on polytopes

Gillette, Andrew; Rand, Alexander

ESAIM: Mathematical Modelling and Numerical Analysis , Special Issue – Polyhedral discretization for PDE, Tome 50 (2016) no. 3, pp. 651-676.

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.

G. Acosta, Lagrange and average interpolation over 3D anisotropic elements. J. Comput. Appl. Math. 135 (2001) 91–109. | DOI | MR | Zbl

G. Acosta and R.G. Durán, 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

P. Antonietti, M. Verani and L. Zikatanov, 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

I. Babuška and A.K. Aziz, 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

L. Beirão Da Veiga, F. Brezzi, A. Cangiani, G. Manzini, L.D. Marini and A. Russo, Basic principles of virtual element methods. Math. Models Methods Appl. Sci. 23 (2013) 199–214. | DOI | MR | Zbl

L. Beirão Da Veiga, F. Brezzi and L.D. Marini, Virtual elements for linear elasticity problems. SIAM J. Numer. Anal. 51 (2013) 794–812. | DOI | MR | Zbl

L. Beirão Da Veiga, F. Brezzi, L. Marini and A. Russo, The hitchhiker’s guide to the virtual element method. Math. Models Methods Appl. Sci. 24 (2014) 1541–1573. | DOI | MR | Zbl

W. Blaschke, 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

J. Bonelle and A. Ern, Analysis of compatible discrete operator schemes for elliptic problems on polyhedral meshes. ESAIM: M2AN 48 (2014) 553–581. | DOI | Numdam | MR | Zbl

J. Bonelle and A. Ern, Analysis of compatible discrete operator schemes for the Stokes equations on polyhedral meshes. IMA J. Numer. Anal. 35 (2015) 1672–1697. | DOI | MR | Zbl

J.H. Bramble and S.R. Hilbert, 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

J. Brandts, S. Korotov and M. Kzříěk, 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

F. Brezzi, A. Buffa and G. Manzini, Mimetic scalar products of discrete differential forms. J. Comput. Phys. 257 (2014) 1228–1259. | DOI | MR | Zbl

F. Brezzi, K. Lipnikov and V. Simoncini, 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.

A. Cangiani, G. Manzini, A. Russo and N. Sukumar, Hourglass stabilization and the virtual element method. Int. J. Numer. Meth. Engng 1 (2014) 1–33. | Zbl

L. Chen and J. Xu, Optimal Delaunay triangulation. J. Comput. Math. 22 (2004) 299–308. | MR | Zbl

S.-W. Cheng, T.K. Dey, H. Edelsbrunner, M.A. Facello and S.-H. Teng, Sliver exudation. J. ACM 47 (2000) 883–904. | DOI | MR | Zbl

L.P. Chew, 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

M. Costabel, Boundary integral operators on Lipschitz domains: elementary results. SIAM J. Math. Anal. 19 (1988) 613–626. | DOI | MR | Zbl

E.F. D’Azevedo and R.B. Simpson, On optimal interpolation triangle incidences. SIAM J. Sci. Stat. Comput. 10 (1989) 1063–1075. | DOI | MR | Zbl

S. Dekel and D. Leviatan, The Bramble–Hilbert lemma for convex domains. SIAM J. Math. Anal. 35 (2004) 1203–1212. | DOI | MR | Zbl

E. Di Nezza, G. Palatucci and E. Valdinoci, Hitchhikers guide to the fractional Sobolev spaces. Bull. Sci. Math. 136 (2012) 521–573. | DOI | MR | Zbl

Z. Ding, A proof of the trace theorem of Sobolev spaces on Lipschitz domains. Proc. Amer. Math. Soc. 124 (1996) 591–600. | DOI | MR | Zbl

R.G. Durán, Error estimates for $3$-d narrow finite elements. Math. Comput. 68 (1999) 187–199. | DOI | MR | Zbl

H. Edelsbrunner and D. Guoy, 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

T. Euler, R. Schuhmann and T. Weiland, 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

M. Floater, Mean value coordinates. Comput. Aided Geom. Des. 20 (2003) 19–27. | DOI | MR | Zbl

M. Floater, A. Gillette and N. Sukumar, Gradient bounds for Wachspress coordinates on polytopes. SIAM J. Numer. Anal. 52 (2014) 515–532. | DOI | MR | Zbl

M. Floater, G. Kós and M. Reimers, Mean value coordinates in 3D. Comput. Aided Geom. Des. 22 (2005) 623–631. | DOI | MR | Zbl

A. Gillette, A. Rand and C. Bajaj, 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

A. Hannukainen, S. Korotov and M. Kzříěk, The maximum angle condition is not necessary for convergence of the finite element method. Numer. Math. 120 (2012) 79–88. | DOI | MR | Zbl

K. Hormann and N. Sukumar, Maximum entropy coordinates for arbitrary polytopes. Comput. Graphics Forum 27 (2008) 1513–1520. | DOI

P. Jamet, 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

P. Joshi, M. Meyer, T. Derose, B. Green and T. Sanocki, Harmonic coordinates for character articulation. ACM Trans. Graphics 26 (2007) 71. | DOI

T. Ju, P. Liepa and J. Warren, A general geometric construction of coordinates in a convex simplicial polytope. Comput. Aided Geom. Des. 24 (2007) 161–178. | DOI | MR | Zbl

T. Ju, S. Schaefer and J. Warren, Mean value coordinates for closed triangular meshes. ACM Trans. Graphics 24 (2005) 561–566. | DOI

K. Kobayashi and T. Tsuchiya, A Babuška-Aziz type proof of the circumradius condition. Jpn J. Ind. Appl. Math. 31 (2014) 193–210. | DOI | MR | Zbl

K. Kobayashi and T. Tsuchiya, On the circumradius condition for piecewise linear triangular elements. Japan J. Ind. Appl. Math. 32 (2015) 65–76. | DOI | MR | Zbl

M. Kzříěk, On semiregular families of triangulations and linear interpolation. Appl. Math. 36 (1991) 223–232. | DOI | MR | Zbl

M. Kzříěk, 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

A. Lemoine, J.-P. Caltagirone, M. Azaïez and S. Vincent, 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

S. Li and W.K. Liu, Meshfree and particle methods and their applications. Appl. Mech. Rev. 55 (2002) 1–34. | DOI

X.-Y. Li, Generating well-shaped $d$-dimensional Delaunay meshes. Theoret. Comput. Sci. 296 (2003) 145–165. | DOI | MR | Zbl

X.-Y. Li and S.-M. Hu, Poisson coordinates. IEEE Trans. Visualization Comput. Graphics 19 (2013) 344–352. | DOI

K. Lipnikov, G. Manzini and M. Shashkov, Mimetic finite difference method. J. Comput. Phys. 257 (2014) 1163–1227. | DOI | MR | Zbl

G. Manzini, A. Russo and N. Sukumar, New perspectives on polygonal and polyhedral finite element methods. Math. Models Methods Appl. Sci. 24 (2014) 1665–1699. | DOI | MR | Zbl

J. Marschall, 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

L. Mu, J. Wang and X. Ye, Weak Galerkin finite element methods on polytopal meshes. Int. J. Numer. Anal. Model. 12 (2015) 31–53. | MR | Zbl

P.L. Powar, Minimal roughness property of the Delaunay triangulation: A shorter approach. Comput. Aided Geom. Des. 9 (1992) 491–494. | DOI | MR | Zbl

J. Rambau, 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

A. Rand, Average interpolation under the maximum angle condition. SIAM J. Numer. Anal. 50 (2012) 2538–2559. | DOI | MR | Zbl

A. Rand, A. Gillette and C. Bajaj, Interpolation error estimates for mean value coordinates. Adv. Comput. Math. 39 (2013) 327–347. | DOI | MR | Zbl

S. Rippa, Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Des. 7 (1990) 489–497. | DOI | MR | Zbl

S. Rippa, Long and thin triangles can be good for linear interpolation. SIAM J. Numer. Anal. 29 (1992) 257–270. | DOI | MR | Zbl

S. Rippa and B. Schiff, Minimum energy triangulations for elliptic problems. Comput. Methods Appl. Mech. Engrg. 84 (1990) 257–274. | DOI | MR | Zbl

E. Schönhardt, Über die zerlegung von dreieckspolyedern in tetraeder. Math. Annal. 98 (1928) 309–312. | DOI | JFM | MR

N.A. Shenk, Uniform error estimates for certain narrow Lagrange finite elements. Math. Comput. 63 (1994) 105–119. | DOI | MR | Zbl

J.R. Shewchuk, General-dimensional constrained Delaunay and constrained regular triangulations, I: Combinatorial properties. Discrete Comput. Geom. 39 (2008) 580–637. | DOI | MR | Zbl

R. Sibson, Locally equiangular triangulations. Comput. J. 21 (1978) 243–245. | DOI | MR

R. Sibson, A vector identity for the Dirichlet tessellation. Math. Proc. Cambridge Philos. Soc. 87 (1980) 151–155. | DOI | MR | Zbl

N. Sukumar, Construction of polygonal interpolants: a maximum entropy approach. Int. J. Numer. Methods Eng. 61 (2004) 2159–2181. | DOI | MR | Zbl

N. Sukumar and R. Wright, 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

N. Sukumar, B. Moran, A. Semenov and V. Belikov, 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

A. Tabarraei and N. Sukumar, Application of polygonal finite elements in linear elasticity. Int. J. Comput. Methods 3 (2006) 503–520. | DOI | MR | Zbl

R. Verfürth, 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

J. Wang and X. Ye, A weak Galerkin finite element method for second-order elliptic problems. J. Comput. Appl. Math. 241 (2013) 103–115. | DOI | MR | Zbl

J. Wang and X. Ye, A weak Galerkin mixed finite element method for second order elliptic problems. Math. Comput. 83 (2014) 2101–2126. | DOI | MR | Zbl

J. Warren, Barycentric coordinates for convex polytopes. Adv. Comput. Math. 6 (1996) 97–108. | DOI | MR | Zbl

J. Warren, S. Schaefer, A.N. Hirani and M. Desbrun, Barycentric coordinates for convex sets. Adv. Comput. Math. 27 (2007) 319–338. | DOI | MR | Zbl

M. Wicke, M. Botsch and M. Gross, 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