×

Functional data approximation on bounded domains using polygonal finite elements. (English) Zbl 1441.65018

Summary: We construct and analyze piecewise approximations of functional data on arbitrary 2D bounded domains using generalized barycentric finite elements, and particularly quadratic serendipity elements for planar polygons. We compare approximation qualities (precision/convergence) of these partition-of-unity finite elements through numerical experiments, using Wachspress coordinates, natural neighbor coordinates, Poisson coordinates, mean value coordinates, and quadratic serendipity bases over polygonal meshes on the domain. For a convex \(n\)-sided polygon, the quadratic serendipity elements have \(2n\) basis functions, associated in a Lagrange-like fashion to each vertex and each edge midpoint, rather than the usual \(n(n + 1) / 2\) basis functions to achieve quadratic convergence. Two greedy algorithms are proposed to generate Voronoi meshes for adaptive functional/scattered data approximations. Experimental results show space/accuracy advantages for these quadratic serendipity finite elements on polygonal domains versus traditional finite elements over simplicial meshes. Polygonal meshes and parameter coefficients of the quadratic serendipity finite elements obtained by our greedy algorithms can be further refined using an \(L_2\)-optimization to improve the piecewise functional approximation. We conduct several experiments to demonstrate the efficacy of our algorithm for modeling features/discontinuities in functional data/image approximation.

MSC:

65D10 Numerical smoothing, curve fitting

Software:

Triangle
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adams, M. D., A flexible content-adaptive mesh-generation strategy for image representation, IEEE Trans. Image Process., 20, 2414-2427, (2011) · Zbl 1372.94003
[2] Adams, M. D., A highly-effective incremental/decremental Delaunay mesh-generation strategy for image representation, Signal Process., 93, 749-764, (2013)
[3] Amirfakhrian, M., Best approximation of multivariate functions in \(l_1\) and \(l_2\) by optimization, Math. Sci., 4, 205-219, (2010) · Zbl 1216.41007
[4] Arnold, D. N.; Awanou, G., The serendipity family of finite elements, Found. Comput. Math., 11, 337-344, (2011) · Zbl 1218.65125
[5] Arnold, D. N.; Boffi, D.; Falk, R. S., Approximation by quadrilateral finite elements, Math. Comput., 71, 909-922, (2002) · Zbl 0993.65125
[6] Cao, J.; Li, X.; Chen, Z.; Qin, H., Spherical DCB-spline surfaces with hierarchical and adaptive knot insertion, IEEE Trans. Vis. Comput. Graph., 18, 1290-1303, (2012)
[7] Carr, J. C.; Beatson, R. K.; Cherrie, J. B.; Mitchell, T. J.; Fright, W. R.; McCallum, B. C.; Evans, T. R., Reconstruction and representation of 3D objects with radial basis functions, (Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, (2001)), 67-76
[8] Chen, Z.; Xiao, Y.; Cao, J., Approximation by piecewise polynomials on Voronoi tessellation, Geometric Modeling and Processing 2014, Graph. Models, 76, 522-531, (2014)
[9] Dahmen, W.; Micchelli, C. A.; Seidel, H.-P., Blossoming begets B-spline bases built better by B-patches, Math. Comput., 59, 97-115, (1992) · Zbl 0757.41014
[10] Dunkl, C. F., Orthogonal polynomials on the hexagon, SIAM J. Appl. Math., 47, 343-351, (1987) · Zbl 0613.33010
[11] Farouki, R. T.; Goodman, T. N.; Sauer, T., Construction of orthogonal bases for polynomials in Bernstein form on triangular and simplex domains, Comput. Aided Geom. Des., 20, 209-230, (2003) · Zbl 1069.65517
[12] Fedele, G.; Ferrise, A., Explicit solution of the finite time \(l_2\)-norm polynomial approximation problem, Appl. Comput. Math., 217, 8354-8359, (2011) · Zbl 1217.41010
[13] Floater, M. S., Generalized barycentric coordinates and applications, Acta Numer., 24, 161-214, (2015) · Zbl 1317.65065
[14] Floater, M. S.; Hormann, K., Surface parameterization: a tutorial and survey, (Advances in Multiresolution for Geometric Modelling, (2005), Springer), 157-186 · Zbl 1065.65030
[15] Floater, M. S.; Lai, M.-J., Polygonal spline spaces and the numerical solution of the Poisson equation, SIAM J. Numer. Anal., 54, 797-824, (2016) · Zbl 1416.65474
[16] Gillette, A.; Bajaj, C., Dual formulations of mixed finite element methods with applications, Comput. Aided Des., 43, 1213-1221, (2011)
[17] Gillette, A.; Rand, A.; Bajaj, C., Error estimates for generalized barycentric coordinates, Adv. Comput. Math., 37, 417-439, (2012) · Zbl 1259.65013
[18] von Golitschek, M.; Lai, M.-J.; Schumaker, L. L., Error bounds for minimal energy bivariate polynomial splines, Numer. Math., 93, 315-331, (2002) · Zbl 1012.41011
[19] Greiner, Günther; Hormann, K., Interpolating and approximating scattered 3D-data with hierarchical tensor product B-splines, (Proceedings of Chamonix, (1996), Citeseer), 1
[20] Hormann, K.; Floater, M. S., Mean value coordinates for arbitrary planar polygons, ACM Trans. Graph. (TOG), 25, 1424-1441, (2006)
[21] Iske, A.; Demaret, L., Optimally sparse image approximation by adaptive linear splines over anisotropic triangulations, (2015 International Conference on Sampling Theory and Applications, (2015), IEEE), 463-467
[22] Lai, M., Multivariate splines for data Fitting and approximation, (Neamtu, M.; Schumaker, L. L., The Conference Proceedings of the 12th Approximation Theory, (2008), Nashboro Press San Antonio) · Zbl 1146.41005
[23] Lai, M.-J.; Schumaker, L. L., Spline functions on triangulations, vol. 110, (2007), Cambridge University Press · Zbl 1185.41001
[24] Lai, M.-J.; Slavov, G., On recursive refinement of convex polygons, Comput. Aided Geom. Des., 45, 83-90, (2016) · Zbl 1418.65024
[25] Li, P.; Adams, M. D., A tuned mesh-generation strategy for image representation based on data-dependent triangulation, IEEE Trans. Image Process., 22, 2004-2018, (2013) · Zbl 1373.94235
[26] Li, X.-Y.; Hu, S.-M., Poisson coordinates, IEEE Trans. Vis. Comput. Graph., 19, 344-352, (2013)
[27] Liu, Y.; Wang, W.; Lévy, B.; Sun, F.; Yan, D.-M.; Lu, L.; Yang, C., On centroidal Voronoi tessellation—energy smoothness and fast computation, ACM Trans. Graph., 28, 1-17, (2009)
[28] Lloyd, S. P., Least squares quantization in PCM, IEEE Trans. Inf. Theory, 28, 129-137, (1982) · Zbl 0504.94015
[29] Mann, S., Cubic precision clough-tocher interpolation, Comput. Aided Geom. Des., 16, 85-88, (1999) · Zbl 0909.68184
[30] Mann, S., A blossoming development of splines, Synth. Lect. Comput. Graph. Animat., 1, 1-108, (2006)
[31] Martin, S.; Kaufmann, P.; Botsch, M.; Wicke, M.; Gross, M., Polyhedral finite elements using harmonic basis functions, (Proc. Symp. Geom. Proc., (2008)), 1521-1529
[32] Milbradt, P.; Pick, T., Polytope finite elements, Int. J. Numer. Methods Eng., 73, 1811-1835, (2008) · Zbl 1162.65406
[33] Nivoliers, V.; Lévy, B., Approximating functions on a mesh with restricted Voronoi diagrams, Comput. Graph. Forum, 32, 83-92, (2013)
[34] Powell, M. J.D., Approximation theory and methods, (1981), Cambridge University Press · Zbl 0453.41001
[35] Powell, M. J.D.; Sabin, M. A., Piecewise quadratic approximations on triangles, ACM Trans. Math. Softw., 3, 316-325, (1977) · Zbl 0375.41010
[36] Rand, A.; Gillette, A.; Bajaj, C., Quadratic serendipity finite elements on polygons using generalized barycentric coordinates, Math. Comput., 83, 2691-2716, (2014) · Zbl 1300.65091
[37] Rashid, M. M.; Selimotic, M., A three-dimensional finite element method with arbitrary polyhedral elements, Int. J. Numer. Methods Eng., 67, 226-252, (2006) · Zbl 1110.74855
[38] Sarkis, M.; Diepold, K., Content adaptive mesh representation of images using binary space partitions, Trans. Image Process., 18, 1069-1079, (2009) · Zbl 1371.94327
[39] Shewchuk, J. R., Delaunay refinement algorithms for triangular mesh generation, Comput. Geom., 22, 21-74, (2002) · Zbl 1016.68139
[40] Sibson, R., A vector identity for the Dirichlet tessellation, Math. Proc. Camb. Philos. Soc., 87, 151-155, (1980) · Zbl 0466.52010
[41] Sieger, D.; Alliez, P.; Botsch, M., Optimizing Voronoi diagrams for polygonal finite element computations, (Proceedings of the 19th International Meshing Roundtable, (2010), Springer), 335-350
[42] Sukumar, N., Quadratic maximum-entropy serendipity shape functions for arbitrary planar polygons, Comput. Methods Appl. Mech. Eng., 263, 27-41, (2013) · Zbl 1286.65168
[43] Sukumar, N.; Malsch, E. A., Recent advances in the construction of polygonal finite element interpolants, Arch. Comput. Methods Eng., 13, 129-163, (2006) · Zbl 1101.65108
[44] Sukumar, N.; Tabarraei, A., Conforming polygonal finite elements, Int. J. Numer. Methods Eng., 61, 2045-2066, (2004) · Zbl 1073.65563
[45] Tabarraei, A.; Sukumar, N., Application of polygonal finite elements in linear elasticity, Int. J. Comput. Methods, 3, 503-520, (2006) · Zbl 1198.74104
[46] Talischi, C.; Paulino, G. H.; Pereira, A.; Menezes, I. F., Polygonal finite elements for topology optimization: a unifying paradigm, Int. J. Numer. Methods Eng., 82, 671-698, (2010) · Zbl 1188.74072
[47] Wachspress, E. L., A rational finite element basis, (1975), Academic Press New York · Zbl 0322.65001
[48] Wicke, M.; Botsch, M.; Gross, M., A finite element method on convex polyhedra, Comput. Graph. Forum, 26, 355-364, (2007)
[49] Zhou, T.; Lai, M.-J., Scattered data interpolation by bivariate splines with higher approximation order, J. Comput. Appl. Math., 242, 125-140, (2013) · Zbl 1255.65034
[50] Zhou, T.; Han, D.; Lai, M.-J., Energy minimization method for scattered data Hermite interpolation, Appl. Numer. Math., 58, 646-659, (2008) · Zbl 1141.65008
[51] Zienkiewicz, O.; Taylor, R., The finite element method, (2000), Butterworth-Heinemann London · Zbl 0991.74002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.