Delaunay refinement algorithms for triangular mesh generation

Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles.

Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin[( , where φ60°is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest.

Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30° (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.     

Triangulation refinement by using edge subdivision

It is proved that any triangulation of a flat polygonal region can be refined by using repeated subdivisions of an edge so that: (1) the maximum diameter of the triangles would be less than any pre-assigned positive number, and (2) the minimum interior angle of the triangles of the triangulation obtained would be not less than the minimum interior angle of the triangles of the original triangulation divided by 9. The required triangulation refinement is constructed in two steps: first, the triangulation is refined so that the triangles of the triangulation obtained can be combined into pairs, and only boundary triangles may be left unpaired; at this step each triangle is split into at most 4 parts. Then the triangulation obtained is refined once again in order that the diameter of each triangle be less then a prescribed ?. At each of the steps, the minimum interior angle of triangles is reduced by at most 3 times. This is guaranteed by the lemma saying that the interior angles of the triangles into which the original triangle is divided by a median are at least as great as one-third of the minimum interior angle of the original triangle.     

Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations

We introduce a new type of Steiner points, called off-centers, as an alternative to circumcenters, to improve the quality of Delaunay triangulations in two dimensions. We propose a new Delaunay refinement algorithm based on iterative insertion of off-centers. We show that this new algorithm has the same quality and size optimality guarantees of the best known refinement algorithms. In practice, however, the new algorithm inserts fewer Steiner points, runs faster, and generates smaller triangulations than the best previous algorithms. Performance improvements are significant especially when user-specified minimum angle is large, e.g., when the smallest angle in the output triangulation is 30°, the number of Steiner points is reduced by about 40%, while the mesh size is down by about 30%. As a result of its shown benefits, the algorithm described here has already replaced the well-known circumcenter insertion algorithm of Ruppert and has been the default quality triangulation method in the popular meshing software Triangle.¹     

Hot spots conjecture for a class of acute triangles

We show that the hot spots conjecture of J. Rauch holds for acute triangles if one of the angles is not larger than \(\pi /6\). More precisely, we show that the second Neumann eigenfunction on those acute triangles has no maximum or minimum inside the domain. We first simplify the problem by showing that absence of critical points on two sides implies no critical points inside a triangle. This result applies to any acute triangle and might help prove the conjecture for arbitrary acute triangles. Then we show that there are no critical points on two sides assuming one small angle. We also establish simplicity for the smallest positive Neumann eigenvalue for all non-equilateral acute triangles. This result was already known for obtuse triangles, and it fails for the equilateral case.     

Approximating the minimum weight steiner triangulation

We show that the length of the minimum weight Steiner triangulation (MWST) of a point set can be approximated within a constant factor by a triangulation algorithm based on quadtrees. InO(n logn) time we can compute a triangulation withO(n) new points, and no obtuse triangles, that approximates the MWST. We can also approximate the MWST with triangulations having no sharp angles. We generalize some of our results to higher-dimensional triangulation problems. No previous polynomial-time triangulation algorithm was known to approximate the MWST within a factor better thanO(logn).     

Direct sums of finitary permutation groups

The interpolation problem under consideration is connected with the finite element method in ?³. In most cases, when finite elements are constructed by means of the partition of a given domain in ?² into triangles and interpolation of the Hermite or Birkhoff type, the sine of the smallest angle of the triangle appears in the denominators of the error estimates for the derivatives. In the case of ? ^m (m ≥ 3), the ratio of the radius of the inscribed sphere to the diameter of the simplex is used as an analog of this characteristic. This makes it necessary to impose constraints on the triangulation of the domain. The recent investigations by a number of authors reveal that, in the case of triangles, the smallest angle in the error estimates for some interpolation processes can be replaced by the middle or the greatest one, which makes it possible to weaken the triangulation requirements. There are fewer works of this kind for m ≥ 3, and the error estimates are given there in terms of other characteristics of the simplex. In this paper, methods are suggested for constructing an interpolation third-degree polynomial on a simplex in ?³. These methods allow one to obtain estimates in terms of a new characteristic of a rather simple form and weaken the triangulation requirements.     

On the stability of normalized Powell–Sabin B-splines

In this paper we show that the normalized Powell–Sabin B-splines form a stable basis for the max norm. The approximation constants depend only on the smallest angle in the underlying triangulation. Since the B-splines refer to the size of the Powell–Sabin triangles, we find that small Powell–Sabin triangles yield better approximation constants than big Powell–Sabin triangles. Next, in addition to the max norm, we treat the L_p norm. Here the approximation constants depend also on a fraction proper to the triangulation, thus the B-splines are not stable for the L_p norm. Finally, as a special case, we consider the B-spline bases obtained from Powell–Sabin triangles with minimal area and pay extra attention to the approximation constants for the max norm.     

Optimality of the Delaunay triangulation in ℝ d

In this paper we present new optimality results for the Delaunay triangulation of a set of points in ℝ ^d . These new results are true in all dimensionsd. In particular, we define a power function for a triangulation and show that the Delaunay triangulation minimizes the power function over all triangulations of a point set. We use this result to show that (a) the maximum min-containment radius (the radius of the smallest sphere containing the simplex) of the Delaunay triangulation of a point set in ℝ ^d is less than or equal to the maximum min-containment radius of any other triangulation of the point set, (b) the union of circumballs of triangles incident on an interior point in the Delaunay triangulation of a point set lies inside the union of the circumballs of triangles incident on the same point in any other triangulation of the point set, and (c) the weighted sum of squares of the edge lengths is the smallest for Delaunay triangulation, where the weight is the sum of volumes of the triangles incident on the edge. In addition we show that if a triangulation consists of only self-centered triangles (a simplex whose circumcenter falls inside the simplex), then it is the Delaunay triangulation.     

Lower estimates for the error of approximation of derivatives for composite finite elements with smoothness property

We consider a natural class of composite finite elements that provide the mth-order smoothness of the resulting piecewise polynomial function on a triangulated domain and do not require any information on neighboring elements. It is known that, to provide a required convergence rate in the finite element method, the “smallest angle condition” must be often imposed on the triangulation of the initial domain; i.e., the smallest possible values of the smallest angles of the triangles must be lower bounded. On the other hand, the negative role of the smallest angle can be weakened (but not eliminated completely) by choosing appropriate interpolation conditions. As shown earlier, for a large number of methods of choosing interpolation conditions in the construction of simple (noncomposite) finite elements, including traditional conditions, the influence of the smallest angle of the triangle on the error of approximation of derivatives of a function by derivatives of the interpolation polynomial is essential for a number of derivatives of order 2 and higher for m ≥ 1. In the present paper, a similar result is proved for some class of composite finite elements.     

一类非线性算子障碍问题的Schwarz算法

本文对一类非线性算子的障碍问题提出了几个Schwarz算法,所得迭代序列为上解序列或下解序列,它们单调收敛于问题的准确解.     

Lepp-bisection algorithms,applications and mathematical properties

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods for PDEs. In addition, right-triangle bintree triangulations are multiresolution algorithms used for terrain modeling and real time visualization of terrain applications. These algorithms are based on the properties of the consecutive bisection of a triangle by the median of the longest edge, and can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, which implies the use of very local refinement operations over fully conforming meshes (where the intersection of pairs of neighbor triangles is either a common edge or a common vertex). In this paper we review the Lepp-bisection algorithms, their properties and applications. To the end we use recent simpler and stronger results on the complexity aspects of the bisection method and its geometrical properties. We discuss and analyze the computational costs of the algorithms. The generalization of the algorithms to 3-dimensions is also discussed. Applications of these methods are presented: for serial and parallel view dependent level of detail terrain rendering, and for the parallel refinement of tetrahedral meshes.     

一类T单调算子障碍问题的块单调迭代法

本文对一类T单调算子的障碍问题提出了几个块迭代法．所得的迭代序列为上解序列和下解序列,它们均单调收敛于问题的准确解,本文建立了这些算法的比较定理．     

Construction of Normalized B-Splines for a Family of Smooth Spline Spaces Over Powell–Sabin Triangulations

We construct a suitable B-spline representation for a family of bivariate spline functions with smoothness r≥1 and polynomial degree 3r?1. They are defined on a triangulation with Powell–Sabin refinement. The basis functions have a local support, they are nonnegative, and they form a partition of unity. The construction involves the determination of triangles that must contain a specific set of points. We further consider a number of CAGD applications. We show how to define control points and control polynomials (of degree 2r?1), and we provide an efficient and stable computation of the Bernstein–Bézier form of such splines.     

Multithread parallelization of Lepp-bisection algorithms

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods. They can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, to refine the target triangles and some related neighbors. We discuss a parallel multithread algorithm, where every thread is in charge of refining a triangle t and its associated Lepp neighbors. The thread manages a changing Lepp(t) (ordered set of increasing triangles) both to find a last longest (terminal) edge and to refine the pair of triangles sharing this edge. The process is repeated until triangle t is destroyed. We discuss the algorithm, related synchronization issues, and the properties inherited from the serial algorithm. We present an empirical study that shows that a reasonably efficient parallel method with good scalability was obtained.     

Data Dependent Triangulations for Piecewise Linear Interpolation

Given a set of data points in R² and corresponding data values,it is clear that the quality of a piecewise linear interpolationover triangles depends on the specific triangulation of thedata points. While conventional triangulation methods dependonly on the distribution of the data points in R² in this paperwe suggest that the triangulation should depend on the datavalues as well. Several data dependent criteria for definingthe triangulation are discussed and efficient algorithms forcomputing these triangulations are presented. It is shown fora variety of test cases that data dependent triangulations canimprove significantly the quality of approximation and thatlong and thin triangles, which are traditionally avoided, aresometimes very suitable.     

Precise bounds and asymptotics for the first Dirichlet eigenvalue of triangles and rhombi

We study the asymptotic expansion of the first Dirichlet eigenvalue of certain families of triangles and of rhombi as a singular limit is approached. In certain cases, which include isosceles and right triangles, we obtain the exact value of all the coefficients of the unbounded terms in the asymptotic expansion as the angle opening approaches zero, plus the constant term and estimates on the remainder. For rhombi and other triangle families such as isosceles triangles where now the angle opening approaches π, we have the first two terms plus bounds on the remainder. These results are based on new upper and lower bounds for these domains whose asymptotic expansions coincide up to the orders mentioned. Apart from being accurate near the singular limits considered, our lower bounds for the rhombus improve upon the bound by Hooker and Protter for angles up to approximately 22° and in the range (31°,54°). These results also show that the asymptotic expansion around the degenerate case of the isosceles triangle with vanishing angle opening depends on the path used to approach it.     

A TQFT of Turaev–Viro Type on Shaped Triangulations

A shaped triangulation is a finite triangulation of an oriented pseudo-three-manifold where each tetrahedron carries dihedral angles of an ideal hyperbolic tetrahedron. To each shaped triangulation, we associate a quantum partition function in the form of an absolutely convergent state integral which is invariant under shaped 3–2 Pachner moves and invariant with respect to shape gauge transformations generated by total dihedral angles around internal edges through the Neumann–Zagier Poisson bracket. Similarly to Turaev–Viro theory, the state variables live on edges of the triangulation but take their values on the whole real axis. The tetrahedral weight functions are composed of three hyperbolic gamma functions in a way that they enjoy a manifest tetrahedral symmetry. We conjecture that for shaped triangulations of closed three-manifolds, our partition function is twice the absolute value squared of the partition function of Techmüller TQFT defined by Andersen and Kashaev. This is similar to the known relationship between the Turaev–Viro and the Witten–Reshetikhin–Turaev invariants of three-manifolds. We also discuss interpretations of our construction in terms of three-dimensional supersymmetric field theories related to triangulated three-dimensional manifolds.     

MONOTONIC ITERATIVE ALGORITHMS FOR A QUASICOMPLEMENTARITY PROBLEM

1. IntroductionConsider the following QCP: find u E Re such thatwhere A, B: R" -+ Re are operators, f E R". The quasivariational inequality which is equivalent to (1) sounds: to find u E Re such that u 2 Ba andIf Ba = c E R" for ally v E R" then QCP(1) reduces into CP. (1) appears in mathematicalprogramming (see, for example, [2] and the references therein), also comes from the discretization of QCP in mathematical physics and control theory (see [1]). For various generalization,see…     

Algorithms for optimal area triangulations of a convex polygon

Given a convex polygon with n vertices in the plane, we are interested in triangulations of its interior, i.e., maximal sets of non-intersecting diagonals that subdivide the interior of the polygon into triangles. The MaxMin area triangulation is the triangulation of the polygon that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. We present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in O(n²logn) time and O(n²) space. The algorithms use dynamic programming and a number of geometric properties that are established within the paper.     

Approximation of the Normal Vector Field and the Area of a Smooth Surface

This paper deals with the comparison of the normal vector field of a smooth surface S with the normal vector field of another surface differentiable almost everywhere. The main result gives an upper bound on angles between the normals of S and the normals of a triangulation T close to S. This upper bound is expressed in terms of the geometry of T, the curvature of S and the Hausdorff distance between both surfaces. This kind of result is really useful: in particular, results of the approximation of the normal vector field of a smooth surface S can induce results of the approximation of the area; indeed, in a very general case (T is only supposed to be locally the graph of a lipschitz function), if we know the angle between the normals of both surfaces, then we can explicitly express the area of S in terms of geometrical invariants of T, the curvature of S and of the Hausdorff distance between both surfaces. We also apply our results in surface reconstruction: we obtain convergence results when T is the restricted Delaunay triangulation of an -sample of S; using Chews algorithm, we also build sequences of triangulations inscribed in S whose curvature measures tend to the curvatures measures of S.