Hybrid Voronoi Mesh Generation: Algorithms and Unsolved Problems

We consider problem of constructing Voronoi mesh where the union of Voronoi cells approximates the computational domain with a piecewise smooth boundary. In the 2d case the smooth boundary fragments are approximated by the Voronoi edges and Voronoi vertices are placed near summits of sharp boundary...

Full description

Saved in:
Bibliographic Details
Published in:Computational mathematics and mathematical physics 2019-12, Vol.59 (12), p.1945-1964
Main Authors: Garanzha, V. A., Kudryavtseva, L. N., Tsvetkova, V. O.
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Boundary layers
Computational Mathematics and Numerical Analysis
Corners
Domains
Graph theory
Hybrid structures
Mathematics
Mathematics and Statistics
Mesh generation
Polygons
Smooth boundaries
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider problem of constructing Voronoi mesh where the union of Voronoi cells approximates the computational domain with a piecewise smooth boundary. In the 2d case the smooth boundary fragments are approximated by the Voronoi edges and Voronoi vertices are placed near summits of sharp boundary corners. We suggest self-organization meshing algorithm which covers the boundary of domain by an almost-structured band of non-simplicial Delaunay cells. This band consists of quadrangles on the smooth boundary segment and convex polygons around sharp corners. Dual Voronoi mesh is double layered orthogonal structure where central line of the layer approximates the boundary. Overall Voronoi mesh has a hybrid structure and consists of high quality convex polygons in the core of the domain and orthogonal layered structure near boundaries. We introduce refinement schemes for the Voronoi boundary layers, in particular near sharp corners. In the case when the boundary of domain is defined explicitly we suggest Voronoi meshing algorithm based on circle placement on the boundary. We discuss problems related to 3d case generalization of suggested algorithm and illustrate ideas and difficulties on relatively simple 3d test cases.
ISSN:0965-5425
1555-6662
DOI:10.1134/S0965542519120078