Generation of Orthogonal Grids on Curvilinear Trimmed Regions in Constant Time

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


We propose a new algorithm for the generation of orthogonal grids on regions bounded by arbitrary number of polynomial inequalities. Instead of calculation of the grid nodes positions for a particular region, we perform all calculations for general polynomials given with indeterminate coefficients. The first advantage of this approach is that the calculations can be performed only once and then used to generate grids on arbitrary regions and of arbitrary mesh size with constant computational costs. The second advantage of our algorithm is the avoidance of singularities, which occur while using the existing algebraic grid generation methods and lead to the intersection of grid lines. All symbolic calculation can be performed with general purpose Computer Algebra Systems, and expressions obtained in this way can be translated in Java/C++ code.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer, Heidelberg (2003)zbMATHGoogle Scholar
  2. 2.
    Bruce, J.W., Giblin, P.J.: Curves and Singularities. Cambridge University Press, Cambridge (1984)zbMATHGoogle Scholar
  3. 3.
    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
  4. 4.
    Canny, J.: Improved algorithms for sign-determination and existential quantifier elimination. Computer Journal 36, 409–418 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and Algorithms. Springer, Heidelberg (1996)zbMATHGoogle Scholar
  6. 6.
    Eiseman, P.R.: A multi-surface method of coordinate generation. J. Comp. Phys. 33, 118–150 (1979)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Fletcher, C.A.J.: Computational Techniques for Fluid Dynamics, 3rd edn. Springer, Heidelberg (1996)Google Scholar
  8. 8.
    Knupp, P., Steinberg, S.: Fundamentals of Grid Generation. CRC Press, Boca Raton (1994)zbMATHGoogle Scholar
  9. 9.
    Nakamura, S.: Marching grid generation using parabolic partial differential equations. In: Thompson, J.F. (ed.) Numerical Grid generation, pp. 775–786 (1982)Google Scholar
  10. 10.
    Semenov, A.Y.: Marching noniterative generation of orthogonal grids. In: Grid Generation: New Trends and Applications in Real-World Simulations. In: Ivanenko, S.A., Garanzha, V.A. (eds.) Proc. Minisymp. in Int. Conf. Optimiz. Finite-Element Approximations, Splines and Wavelets, St. Petersburg, June 25–29, pp. 100–114. Computing Centre of the Russian Academy of Sciences, Moscow (2001)Google Scholar
  11. 11.
    Steger, J.L., Chaussee, D.S.: Generation of body-fitted coordinates using hyperbolic partial differential equations, SIAM J. Sci. Stat. Comput. 1, 431–437 (1980)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Thompson, J.F., Soni, B.K., Weatherill, N.P. (eds.): Handbook of Grid Generation. CRC Press, Boca Raton (1999)zbMATHGoogle Scholar
  13. 13.
    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 2005

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