A Study on Mesh Generation

The goal of mesh generation is to decompose a geometric domain into simple elements. For example, the square on the left in Figure 1 is decomposed into triangles. A discrete description of a space allows for discrete approximations to functions on that space. Thus, mesh generation is ubiquitous in physical simulation where it allows for the numerical solution to partial differential equations.

The Voronoi diagram is dual to the Delaunay triangulation. It decomposes the plane into polygons called Voronoi cells, one for each q E P, such that the Voronoi cell of q is the set of all points whose nearest neighbor in P is q. Figure 1 shows a simple example of a Delaunay triangulation and a Voronoi diagram on the same set of points. There is a natural way to define Delaunay triangulations and Voronoi diagrams in higher dimensions. One advantage of using the Delaunay triangulation for mesh generation is that it gives a unique decomposition of space defined only by the set of vertices. Thus, we will speak primarily about point sets and the decomposition will be secondary, used mainly for definitions and proofs. Let P be a set of n points in Rd. A mesh generation algorithm will output a superset M of P such that the Voronoi cells have aspect ratio at least some constant. That is, the cells (modulo some on the boundary) should all be sufficiently “round”. The set M along with the Delaunay triangulation of M is called the mesh. The extra points added are called Steiner points. The size of the mesh is its number of points, |M|. This is to be distinguished from the complexity of Vor M, which is the number of cells in the Voronoi diagram of M. We will focus on three main goals of mesh generation: 1. The mesh should conform to a set of input points. That is, every input point should appear as a vertex in the output. 2. The mesh should satisfy some quality condition. That is, every cell in the output should be geometrically “nice”, where several different metrics of quality are used in practice. 3. The mesh should have optimal size. Up to constant factors, no other conforming, quality mesh can have fewer vertices. For many meshing applications, the conforming condition is extended to also include higher order features such as edges, faces, or even piecewise-smooth complexes. In this thesis, we limit the input to points, which is most relevant when using meshes to do data analysis; the input points are the data. There are several metrics used to measure the quality of a mesh. For example, in 2D triangulation, the measure of the smallest angle is commonly used. The idea behind these quality metrics is to give a purely geometric condition that can give guarantees about how well a mesh will work for a given application. For example, the quality a mesh influences the quality of a solution in finite element analysis. Much work has been done on mesh quality measures for discussion on mesh quality conditions relevant to Delaunay meshing. For triangulations and other simplicial meshes, the ratio of the circum radius to the shortest edge may be used in place of the angle condition. A similar notion of quality may be defined on the Voronoi diagram. It is called the These quality conditions may leave some simplices called slivers which are known to be problematic in physical simulation. However, there are many theoretical and practical approaches to dealing with slivers in meshes [CDE+00, ELM+00, Li00, LT01, EG02, Li03, Lab06]. Despite this wealth of research directed at removing slivers, it remains a major research problem in mesh generation. Figure 4 shows an example of a set of points, its Voronoi diagram, and the Voronoi diagram after Steiner points were added. Note that the Voronoi cells of the input points are long and skinny, whereas the output Voronoi cells are round. The third goal of size optimality requires lower bounds. To prove these lower bounds, we use the Ruppert local feature size fP : Rd -> R20, defined as the distance to the second nearest

Point of P. Ruppert’s seminal result on the analysis of 2-dimensional Delaunay refinement reduces the problem of bounding the mesh size to a geometric problem of bounding the integral of a certain measure over the input domain Ώ. His method generalizes naturally to Rd to give the following. Note that the statement here contains a big-θ and not a big-O. Consequently, the analysis doesn’t guarantees the result will be “optimal”. This may seem a bit strange with respect to traditional analysis of algorithms. While it does yield a guarantee of “optimality”, it does not yield a simple description of the asymptotic complexity as a function of n. That is, we don’t get a clear explanation of what optimal means. In fact, the bound cannot be stated directly as a function of n because the integral depends on geometric properties of the input P and the input domain. We could try to add another parameter to capture this geometric structure of the input. For example, letting Δ denote the spread of the input (the ratio of the largest to smallest pair-wise distances), it is not difficult to prove that |M| = O (n log Δ).

This is a conceptual improvement in that it may be easier to think about and write down such a bound, but it adds a good deal of slack. There are simple examples such that |M| = O(n). That is, the contribution of each point is the change in the log of its feature size before and after insertion. The fraction θi is close to 1 when pi is roughly equidistant from its nearest and second nearest neighbors among the first i − 1 points. We say pi is $-medial if $i is larger than some constant θ. When θ is understood, we just say pi is medial. If there exists an input ordering so that each pi is medial then the output size will be O(n). The new bound is asymptotically tight. It also gives an important new insight into the way that we analyze mesh sizing. It reduces the analysis to finding an ordering. For example, to show that an output mesh has linear size, it suffices to find a well-paced ordering, i.e. one such that each pi is medial. Such an ordering is not guaranteed to exist. Sometimes, it is possible to turn an analytic tool into an algorithm. For example, one could hope to build a meshing algorithm that works by explicitly or implicitly finding an ordering that maximizes θi. It turns out that this is exactly what happens in the Sparse Voronoi Refinement (SVR) algorithm of Hudson et al . In SVR, the mesh is constructed incrementally. An input point is inserted only if it is medial. Otherwise, a Steiner point is added. The running time of SVR is O(n log% + |M|). Thus, we see a return of

We replace the usual quality condition on the aspect ratio of Voronoi cells with a notion of hierarchical quality in which the domain is partitioned into a hierarchical tree of sets so that although individual Voronoi cells may have bad aspect ratio, the union of all the cells in a sub-tree does have good aspect ratio. This insight strengthens the analogy of Voronoi refinement mesh generation with the closely related class of algorithms that use compressed quad-trees. The result is Net Mesh, the first algorithm to achieve optimal O(n log n+|M|) running time for conforming mesh generation of point sets. Moreover, Net Mesh can return a hierarchical quality mesh of size O(n) in O(n log n) time. The Ruppert lower bound required us to leave the class of bounded aspect ratio Voronoi diagrams in order to guarantee a linear size output on all inputs. The Net Mesh algorithm can be modified to produce Voronoi diagrams in which every cell is fat, the ratio of the radii of smallest containing ball and the largest contained ball is bounded by some constant. This is very close to the usual definition of quality for Voronoi diagrams; it only relaxes the requirement that the aspect ratio be measured with respect to balls centered at the point generating the Voronoi cell.

• Boris Aronov, Mark de Berg, and Chris Gray. Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. Computational Geometry: Theory and Applications, 41:68–76, 2008. 5.2

• Umut A. Acar, Benoˆıt Hudson, Gary L. Miller, and Todd Phillips. SVR: Practical engineering of a fast 3D meshing algorithm. In Proc. 16th International Meshing Roundtable, pages 45–62, 2007. 4.15, 7.7

• Ivo Babuˇska and A. K. Aziz. On the Angle Condition in the Finite Element Method. SIAM Journal on Numerical Analysis, 13(2):214–226, April 1976. 1.1

• Alexander Barvinok. A Course in Convexity. American Mathematical Society, 2002.

• Marcin Bienkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, and Christian Sohler. Average case complexity of Voronoi diagrams of n sites from the unit cube. In EWCG: European Workshop Comput. Geom., pages 167–170, 2005.

generation. J. Computer & Systems Sciences, 48(3):384–409, June 1994. Special issue for 31st FOCS. 4.2

• M. Bern, D. Eppstein, and S.-H. Teng. Parallel construction of quadtrees and quality triangulations. International Journal of Computational Geometry and Applications (IJCGA), 9(6):517–532, 1999. 4.2

• Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14, pages 585–591, 2001.

• Gunnar Carlsson. Topology and data. Bull. Amer. Math. Soc., 46:255–308, 2009.