×

zbMATH — the first resource for mathematics

Grid generation and optimization based on centroidal Voronoi tessellations. (English) Zbl 1024.65118
Summary: Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a region such that the generating points of the tessellations are also the centroids of the corresponding Voronoi regions. Such tessellations are of use in very diverse applications, including data compression, clustering analysis, cell biology, territorial behavior of animals, and optimal allocation of resources.
In this paper, we explore the use of CVTs in grid generation in connection with finite element approximations of partial differential equations. We describe these tessellations and methods for their determination. We then discuss their application to mesh generation and finish with some examples of their use for the solution of partial differential equations.

MSC:
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
Software:
Qhull; Voronoi
PDF BibTeX Cite
Full Text: DOI
References:
[1] Aurenhammer, F., Voronoi diagrams – a survey of a fundamental geometric data structure, Comp. surveys, 23, 345-405, (1991)
[2] Babuška, I.; Rheinboldt, W., Error estimates for adaptive finite element computations, SIAM J. numer. anal., 15, 736-754, (1978) · Zbl 0398.65069
[3] Barber, C.; Dobkin, D.; Huhdanpaa, H., The quickhull algorithm for convex hulls, ACM trans. math. soft., 22, 469-483, (1996) · Zbl 0884.65145
[4] Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (), 23-90
[5] L. Chew, Guaranteed-quality triangular meshes, Department of Computer Science, Technical Report 89-983, Cornell University, 1989
[6] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM rev., 41, 637-676, (1999) · Zbl 0983.65021
[7] Eiseman, P., Adaptive grid generation, Comput. methods appl. mech. engrg., 64, 321-376, (1987) · Zbl 0636.65126
[8] Fortune, S., Voronoi diagrams and Delaunay triangulations, (), 193-233 · Zbl 0907.68190
[9] Freitag, L.; Jones, M.; Plassmann, P., A parallel algorithm for mesh smoothing, SIAM J. sci. comput., 20, 2023-2040, (1999) · Zbl 0939.65132
[10] Frey, P.; Borouchaki, H.; George, P., Delaunay tetrahedralization using an advancing-front approach, (), 87-106
[11] Frey, P.; Borouchaki, H.; George, P., 3D Delaunay mesh generation coupled with an advancing-front approach, Comput. methods appl. mech. engrg., 157, 115-131, (1998) · Zbl 0947.65130
[12] Gersho, A., Asymptotically optimal block quantization, IEEE trans. inform. theory, 25, 373-380, (1979) · Zbl 0409.94013
[13] Gray, R.; Neuhoff, D., Quantization, IEEE trans. inform. theory, 44, 2325-2383, (1998) · Zbl 1016.94016
[14] Guibas, L.; Knuth, D.; Sharir, M., Randomized incremental construction of Delaunay and voronoı̆ diagrams, Algorithmica, 7, 381-413, (1992) · Zbl 0743.68128
[15] L. Ju, Q. Du, M. Gunzburger, Probablistic methods for centroidal Voronoı̆ tessellations and their parallel implementations, to appear in Parallel Computing
[16] Klein, R., Concrete and abstract Voronoi diagrams, Lecture notes in computer science, vol. 400, (1989), Springer Berlin
[17] Lloyd, S., Least square quantization in PCM, IEEE trans. inform. theory, 28, 129-137, (1982) · Zbl 0504.94015
[18] MacQueen, J., Some methods for classification and analysis of multivariate observations, (), 281-297 · Zbl 0214.46201
[19] McRae, D.; Laflin, K., Dynamic grid adaptation and grid quality, (), 34.1-34.33
[20] Miller, G.; Talmor, D.; Teng, S.; Walkington, N., A Delaunay based numerical method for three dimensions: generation, formulation and partition, (), 683-692 · Zbl 0978.68575
[21] Miller, G.; Talmor, D.; Teng, S.; Walkington, N.; Wang, H., Control volume meshes using sphere packing: generation, refinement and coarsening, (), 47-62
[22] Okabe, A.; Boots, B.; Sugihara, K., Spatial tessellations, concepts and applications of Voronoi diagrams, (1992), Wiley Chichester · Zbl 0877.52010
[23] Rajan, V., Optimality of the Delaunay triangulation in Rd, Discrete comput. geom., 12, 189-202, (1994) · Zbl 0808.52012
[24] Ruppert, J., A Delaunay refinement algorithm for quality 2-dimensional mesh generation, J. algorithms, 18, 548-585, (1995) · Zbl 0828.68122
[25] ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.