On the Provably Tight Approximation of Optimal Meshing for Non-convex Regions

  • Dmytro Chibisov
  • Victor Ganzha
  • Ernst W. Mayr
  • Evgenii V. Vorozhtsov
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4194)


Automatic generation of smooth, non-overlapping meshes on arbitrary regions is the well-known problem. Considered as optimization task the problem may be reduced to finding a minimizer of the weighted combination of so-called length, area, and orthogonality functionals. Unfortunately, it has been shown that on the one hand, certain weights of the individual functionals do not admit the unique optimizer on certain geometric domains. On the other hand, some combinations of these functionals lead to the lack of ellipticity of corresponding Euler-Lagrange equations, and finding the optimal grid becomes computationally too expensive for practical applications. Choosing the right functional for the particular geometric domain of interest may improve the grid generation very much, but choosing the functional parameters is usually done in the trial and error way and depends very much on the geometric domain. This makes the automatic and robust grid generation impossible. Thus, in the present paper we consider the way to compute certain approximations of minimizer of grid functionals independently of the particular domain. Namely, we are looking for the approximation of the minimizer of the individual grid functionals in the local sense. This means the functional has to be satisfied on the possible largest parts of the domain. In particular, we shall show that the so called method of envelopes, otherwise called the method of rolling circle, that has been proposed in our previous paper, guarantees the optimality with respect to the area and orthogonality functionals in this local sense. In the global sense, the grids computed with the aid of envelopes, can be considered as approximations of the optimal solution. We will give the comparison of the method of envelopes with well established Winslow generator by presenting computational results on selected domains with different mesh size.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bruce, J.W., Giblin, P.J.: Curves and Singularities. Cambridge University Press, Cambridge (1984)zbMATHGoogle Scholar
  2. 2.
    Bungartz, H.-J.: Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poisson-Gleichung. Dissertation, Institut für Informatik, Technische Universitait München (1992)Google Scholar
  3. 3.
    Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and Algorithms. Springer, Berlin (1996)zbMATHGoogle Scholar
  4. 4.
    Chibisov, D., Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V.: Generation of orthogonal grids on curvilinear trimmed regions in constant time. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 105–114. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  5. 5.
    Ganzha, V.G., Vorozhtsov, E.V.: Numerical Solution for Partial Differential Equations: Problem Solving Using Mathematica. CRC Press, Boca Raton (1996)Google Scholar
  6. 6.
    Knupp, P., Steinberg, S.: Fundamentals of Grid Generation. CRC Press, Boca Raton (1994)zbMATHGoogle Scholar
  7. 7.
    Peaceman, D.W., Rachford Jr., H.H.: The numerical solution of parabolic and elliptic differential equations. J. of SIAM 3, 28–41 (1955)zbMATHMathSciNetGoogle Scholar
  8. 8.
    Zenger, C.: Sparse grids. In: Parallel Algorithms for Partial Differential Equations. In: Hackbusch, W. (ed.) Proc. Sixth GAMM-Seminar, Kiel, 1990. Notes on Num. Fluid Mech, vol. 31, pp. 241–251. Vieweg-Verlag, Braunschweig/ Wiesbaden (1991)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Dmytro Chibisov
    • 1
  • Victor Ganzha
    • 1
  • Ernst W. Mayr
    • 1
  • Evgenii V. Vorozhtsov
    • 2
  1. 1.Institute of InformaticsTechnical University of MunichGarchingGermany
  2. 2.Institute of Theoretical and Applied MechanicsRussian Academy of SciencesNovosibirskRussia

Personalised recommendations