Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Greedy bisection generates optimally adapted triangulations

Authors: Jean-Marie Mirebeau and Albert Cohen
Journal: Math. Comp. 81 (2012), 811-837
MSC (2010): Primary 65-XX; Secondary 41-XX
Published electronically: September 28, 2011
MathSciNet review: 2869038
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the properties of a simple greedy algorithm for the generation of data-adapted anisotropic triangulations. Given a function $ f$, the algorithm produces nested triangulations $ \mathcal {T}_N$ and corresponding piecewise polynomial approximations $ f_N$ of $ f$. The refinement procedure picks the triangle which maximizes the local $ L^p$ approximation error, and bisects it in a direction which is chosen so to minimize this error at the next step. We study the approximation error in the $ L^p$ norm when the algorithm is applied to $ C^2$ functions with piecewise linear approximations. We prove that as the algorithm progresses, the triangles tend to adopt an optimal aspect ratio which is dictated by the local hessian of $ f$. For convex functions, we also prove that the adaptive triangulations satisfy the convergence bound $ \Vert f-f_N\Vert _{L^p} \leq CN^{-1}\Vert\sqrt {\det (d^2f)}\Vert _{L^\tau }$ with $ \frac 1 \tau :=\frac 1 p + 1$, which is known to be asymptotically optimal among all possible triangulations.

References [Enhancements On Off] (What's this?)

  • 1. V. Babenko, Y. Babenko, A. Ligun and A. Shumeiko, On asymptotical behavior of the optimal linear spline interpolation error of $ C^2$ functions, East J. Approx. 12(1), 71-101, 2006. MR 2294672 (2007m:41008)
  • 2. P. Binev, W. Dahmen, R. DeVore and P. Petrushev, Approximation classes for adaptive methods, Serdica Math. J. 28, 391-416, 2002. MR 1965238 (2004b:65176)
  • 3. H. Borouchaki, P.J. Frey, P.L. George, P. Laug and E. Saltel, Mesh generation and mesh adaptivity: theory, techniques, in Encyclopedia of computational mechanics, E. Stein, R. de Borst and T.J.R. Hughes ed., John Wiley & Sons Ltd., 2004.
  • 4. W. Cao, On the error of linear interpolation and the orientation, aspect ratio, and internal angles of a triangle, SIAM J. Numer. Anal. 43(1), 19-40, 2005. MR 2177954 (2006k:65023)
  • 5. L. Chen, On minimizing the linear interpolation error of convex quadratic functions, East Journal of Approximation 14(3), 271-284, 2008. MR 2441084 (2009h:41002)
  • 6. L. Chen, Mesh smoothing schemes based on optimal Delaunay triangulations, in 13th International Meshing Roundtable, 109-120, Williamsburg, VA, Sandia National Laboratories, 2004.
  • 7. L. Chen, P. Sun and J. Xu, Optimal anisotropic meshes for minimizing interpolation error in $ L^p$-norm, Math. of Comp. 76, 179-204, 2007. MR 2261017 (2008e:65385)
  • 8. A. Cohen, N. Dyn, F. Hecht and J.-M. Mirebeau, Adaptive multiresolution analysis based on anisotropic triangulations, Math. of Comp. 81 (2012), no. 278, 789--810.
  • 9. R. DeVore, Nonlinear approximation, Acta Numerica 51-150, 1998 MR 1689432 (2001a:41034)
  • 10. J.-M. Mirebeau, Optimal bidimensional finite element meshes, preprint, Laboratoire J.-L. Lions.
  • 11. M.C. Rivara, New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations, Int. J. Num. Methods 40, 3313-3324, 1997. MR 1471613

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65-XX, 41-XX

Retrieve articles in all journals with MSC (2010): 65-XX, 41-XX

Additional Information

Jean-Marie Mirebeau
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France

Albert Cohen
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France-

Received by editor(s): October 20, 2008
Received by editor(s) in revised form: June 15, 2010
Published electronically: September 28, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society