You are here

Centroidal Voronoi Tessellations for Mesh Generation

Title: Centroidal Voronoi Tessellations for Mesh Generation: from Uniform to Anisotropic Adaptive Triangulations.
Name(s): Nguyen, Hoa V., author
Gunzburger, Max D., professor directing dissertation
El-Azab, Anter, outside committee member
Peterson, Janet, committee member
Wang, Xiaoming, committee member
Wang, Xiaoqiang, committee member
Department of Mathematics, degree granting department
Florida State University, degree granting institution
Type of Resource: text
Genre: Text
Issuance: monographic
Date Issued: 2008
Publisher: Florida State University
Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource
Language(s): English
Abstract/Description: Mesh generation in regions in Euclidean space is a central task in computational science, especially for commonly used numerical methods for the solution of partial differential equations (PDEs), e.g., finite element and finite volume methods. Mesh generation can be classified into several categories depending on the element sizes (uniform or non-uniform) and shapes (isotropic or anisotropic). Uniform meshes have been well studied and still find application in a wide variety of problems. However, when solving certain types of partial differential equations for which the solution variations are large in some regions of the domain, non-uniform meshes result in more efficient calculations. If the solution changes more rapidly in one direction than in others, non-uniform anisotropic meshes are preferred. In this work, first we present an algorithm to construct uniform isotropic meshes and discuss several mesh quality measures. Secondly we construct an adaptive method which produces non-uniform anisotropic meshes that are well suited for numerically solving PDEs such as the convection diffusion equation. For the uniform Delaunay triangulation of planar regions, we focus on how one selects the positions of the vertices of the triangulation. We discuss a recently developed method, based on the centroidal Voronoi tessellation (CVT) concept, for effecting such triangulations and present two algorithms, including one new one, for CVT-based grid generation. We also compare several methods, including CVT-based methods, for triangulating planar domains. Furthermore, we define several quantitative measures of the quality of uniform grids. We then generate triangulations of several planar regions, including some having complexities that are representative of what one may encounter in practice. We subject the resulting grids to visual and quantitative comparisons and conclude that all the methods considered produce high-quality uniform isotropic grids and that the CVT-based grids are at least as good as any of the others. For more general grid generation settings, e.g., non-uniform and/or anistropic grids, such quantitative comparisons are much more difficult, if not impossible, to either make or interpret. This motivates us to develop CVT-based adaptive non-uniform anisotropic mesh refinement in the context of solving the convection-diffusion equation with emphasis on convection-dominated problems. The challenge in the numerical approximation of this equation is due to large variations in the solution over small regions of the physical domain. Our method not only refines the underlying grid at these regions but also stretches the elements according to the solution variation. Three main ingredients are incorporated to improve the accuracy of numerical solutions and increase the algorithm's robustness and efficiency. First, a streamline upwind Petrov Galerkin method is used to produce a stabilized solution. Second, an adapted metric tensor is computed from the approximate solution. Third, optimized anisotropic meshes are generated from the computed metric tensor. Our algorithm has been tested on a variety of 2-dimensional examples. It is robust in detecting layers and efficient in resolving non-physical oscillations in the numerical approximation.
Identifier: FSU_migr_etd-2616 (IID)
Submitted Note: A Dissertation submitted to the Department of Mathematics in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Degree Awarded: Spring Semester, 2008.
Date of Defense: April 11, 2008.
Keywords: Adaptive Method, Delaunay triangulation, Anisotropic Mesh, Convection-Diffusion Equation
Bibliography Note: Includes bibliographical references.
Advisory Committee: Max D. Gunzburger, Professor Directing Dissertation; Anter El-Azab, Outside Committee Member; Janet Peterson, Committee Member; Xiaoming Wang, Committee Member; Xiaoqiang Wang, Committee Member.
Subject(s): Mathematics
Persistent Link to This Record:
Use and Reproduction: This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). The copyright in theses and dissertations completed at Florida State University is held by the students who author them.
Host Institution: FSU

Choose the citation style.
Nguyen, H. V. (2008). Centroidal Voronoi Tessellations for Mesh Generation: from Uniform to Anisotropic Adaptive Triangulations. Retrieved from