Hybrid Voronoi Mesh Generation: Algorithms and Unsolved Problems

Abstract

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.