article

Approximation by piecewise polynomials on Voronoi tessellation

Authors:

Juan CaoAuthors Info & Claims

Graphical Models, Volume 76, Issue 5

Pages 522 - 531

https://doi.org/10.1016/j.gmod.2014.04.006

Published: 01 September 2014 Publication History

Abstract

We propose a novel method to approximate a function on 2D domain by piecewise polynomials. The Voronoi tessellation is used as a partition of the domain, on which the best fitting polynomials in L^2 metric are constructed. Our method optimizes the domain partition and the fitting polynomials simultaneously by minimizing an objective function indicating the approximation quality. We also provide the explicit formula of the gradient of the objective function, which makes an efficient gradient-based algorithm workable for the function minimization. We conduct several experiments to demonstrate the efficacy of our new approach for generating piecewise polynomial approximations of analytic functions and color images.

References

[1]

Powell, M.J.D., Approximation Theory and Methods. 1981. Cambridge University Press.

[2]

P.K. Agarwal, S. Suri, Surface approximation and geometric partitions, in: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1994, pp. 24-33.

Digital Library

[3]

Prentice, J., Range and domain partitioning in piecewise polynomial approximation. Stud. Math. Sci. v2 i2. 67-77.

[4]

G. Lecot, B. Lévy, Ardeco, Automatic region detection and conversion, in: Proceedings of the 17th Eurographics conference on Rendering Techniques, Eurographics Association, 2006, pp. 349-360.

[5]

Cohen-Steiner, D., Alliez, P. and Desbrun, M., Variational shape approximation. In: ACM Transactions on Graphics (TOG), vol. 23. ACM. pp. 905-914.

[6]

Yan, D.-M., Wang, W., Liu, Y. and Yang, Z., Variational mesh segmentation via quadric surface fitting. Comput.-Aided Des. v44 i11. 1072-1082.

[7]

Nivoliers, V. and Lévy, B., Approximating functions on a mesh with restricted Voronoï diagrams. Comput. Graphics Forum. v32 i5. 83-92.

[8]

Amirfakhrian, M., Best approximation of multivariate functions in L1 and L2 by optimization. Math. Sci. v4 i2. 205-219.

[9]

Fedele, G. and Ferrise, A., Explicit solution of the finite time L2-norm polynomial approximation problem. Appl. Math. Comput. v217 i21. 8354-8359.

[10]

Orthogonal polynomials on the hexagon. SIAM J. Appl. Math. v47 i2. 343-351.

[11]

Farouki, R.T., Goodman, T.N. and Sauer, T., Construction of orthogonal bases for polynomials in bernstein form on triangular and simplex domains. Comput. Aided Geometric Des. v20 i4. 209-230.

[12]

Wu, J. and Kobbelt, L., Structure recovery via hybrid variational surface approximation. Comput. Graphics Forum. v24. 277-284.

[13]

P.D. Simari, K. Singh, Extraction and remeshing of ellipsoidal representations from mesh data, in: Graphics Interface, 2005, pp. 161-168.

[14]

Dyn, N., Levin, D. and Rippa, S., Data dependent triangulations for piecewise linear interpolation. IMA J. Numer. Anal. v10 i1. 137-154.

[15]

Kreylos, O. and Hamann, B., On simulated annealing and the construction of linear spline approximations for scattered data. IEEE Trans. Visual. Comput. Graphics. v7 i1. 17-31.

[16]

Su, D. and Willis, P., Image interpolation by pixel-level data-dependent triangulation. In: Computer Graphics Forum, vol. 23. Wiley Online Library. pp. 189-201.

[17]

Flanders, H., Differentiation under the integral sign. Am. Math. Monthly. v80 i6. 615-627.

[18]

Nocedal, J. and Wright, S.J., Numerical Optimization. 2006. 2nd Edition. Springer.

[19]

A. Fabri, CGAL-the computational geometry algorithm library, in: Proceedings of 10th International Meshing Roundtable, 2001, pp. 137-142.

[20]

Dunavant, D.A., High degree efficient symmetrical Gaussian quadrature rules for the triangle. Int. J. Numer. Methods Eng. v21. 1129-1148.

[21]

Du, Q., Faber, V. and Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. v41. 637-676.

[22]

Alliez, P., Cohen-Steiner, D., Yvinec, M. and Desbrun, M., Variational tetrahedral meshing. ACM Trans. Graphics (Proc. SIGGRAPH). v24 i3. 617-625.

[23]

J.R. Shewchuk, What is a good linear element? Interpolation, conditioning, and quality measures, in: Proc. the 11th International Meshing Roundtable, 2002, pp. 115-126.

[24]

L. Chen, Mesh smoothing schemes based on optimal Delaunay triangulations, in: Proc. 13th International Meshing Roundtable, 2004, pp. 109-120.

[25]

Cao, J., Li, X., Chen, Z. and Qin, H., Spherical DCB-spline surfaces with hierarchical and adaptive knot insertion. IEEE Trans. Visual. Comput. Graphics. v18 i8. 1290-1303.

[26]

Construction of iso-contours, bisectors, and voronoi diagrams on triangulated surfaces. IEEE Trans. Pattern Anal. Mach. Intell. v33 i8. 1502-1517.

[27]

X. Bai, G. Sapiro, A geodesic framework for fast interactive image and video segmentation and matting, in: IEEE 11th International Conference on Computer Vision, 2007, ICCV 2007, IEEE, 2007, pp. 1-8.

[28]

Wang, P., Zeng, G., Gan, R., Wang, J. and Zha, H., Structure-sensitive superpixels via geodesic distance. Int. J. Comput. Vision. v103 i1. 1-21.

Cited By

Waclawek HHuber S(2024)Machine Learning Optimized Orthogonal Basis Piecewise Polynomial ApproximationLearning and Intelligent Optimization10.1007/978-3-031-75623-8_33(427-441)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-75623-8_33
Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Ma DZhou YXin SWang W(2021)Convex and Compact Superpixels by Edge- Constrained Centroidal Power DiagramIEEE Transactions on Image Processing10.1109/TIP.2020.304564030(1825-1839)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1109/TIP.2020.3045640

Approximation by piecewise polynomials on Voronoi tessellation
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Convexifying Positive Polynomials and Sums of Squares Approximation

We show that if a polynomial $f\in \mathbb{R}[x_1,\ldots,x_n]$ is nonnegative on a closed basic semialgebraic set $X=\{x\in\mathbb{R}^n:g_1(x)\ge 0,\ldots,g_r (x)\ge 0\}$, where $g_1,\ldots,g_r\in\mathbb{R}[x_1,\ldots,x_n]$, then $f$ can be approximated ...
On 3-monotone approximation by piecewise polynomials

We consider 3-monotone approximation by piecewise polynomials with prescribed knots. A general theorem is proved, which reduces the problem of 3-monotone uniform approximation of a 3-monotone function, to convex local L"1 approximation of the derivative ...
Nonlinear Approximation from Differentiable Piecewise Polynomials

We study nonlinear n-term approximation in $L_p({\mathbb R}^2)$ ($0<p\le\infty$) from hierarchical sequences of stable local bases consisting of differentiable (i.e., $C^r$ with $r\ge1$) piecewise polynomials (splines). We construct such sequences of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Graphical Models

Graphical Models Volume 76, Issue 5

September, 2014

356 pages

ISSN:1524-0703

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2014.

Publisher

Academic Press Professional, Inc.

United States

Publication History

Published: 01 September 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Waclawek HHuber S(2024)Machine Learning Optimized Orthogonal Basis Piecewise Polynomial ApproximationLearning and Intelligent Optimization10.1007/978-3-031-75623-8_33(427-441)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-75623-8_33
Zhu HCao JXiao YChen ZZhong ZZhang Y(2022)TCB-spline-based Image VectorizationACM Transactions on Graphics10.1145/351313241:3(1-17)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3513132
Ma DZhou YXin SWang W(2021)Convex and Compact Superpixels by Edge- Constrained Centroidal Power DiagramIEEE Transactions on Image Processing10.1109/TIP.2020.304564030(1825-1839)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1109/TIP.2020.3045640

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents