On the sizes of Delaunay meshes

Let be a polyhedral domain occupying a convex volume. We prove that the size of a graded mesh of with bounded vertex degree is within a factor of the size of any Delaunay mesh of with bounded radius-edge ratio. The term depends on the geometry of and it is likely a small constant when the boundaries of are fine triangular meshes. There are several consequences. First, among all Delaunay meshes with bounded radius-edge ratio, those returned by Delaunay refinement algorithms have asymptotically optimal sizes. This is another advantage of meshing with Delaunay refinement algorithms. Second, if no input angle is acute, the minimum Delaunay mesh with bounded radius-edge ratio is not much smaller than any minimum mesh with aspect ratio bounded by a particular constant.     

Polynomial preserving recovery for meshes from Delaunay triangulation or with high aspect ratio

A newly developed polynomial preserving gradient recovery technique is further studied. The results are twofold. First, error bounds for the recovered gradient are established on the Delaunay type mesh when the major part of the triangulation is made of near parallelogram triangle pairs with ε‐perturbation. It is found that the recovered gradient improves the leading term of the error by a factor ε. Secondly, the analysis is performed for a highly anisotropic mesh where the aspect ratio of element sides is unbounded. When the mesh is adapted to the solution that has significant changes in one direction but very little, if any, in another direction, the recovered gradient can be superconvergent. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Boundary-contact problems for domains with edge singularities

We study boundary-contact problems for elliptic equations (and systems) with interfaces that have edge singularities. Such problems represent continuous operators between weighted edge spaces and subspaces with asymptotics. Ellipticity is formulated in terms of a principal symbolic hierarchy, containing interior, transmission, and edge symbols. We construct parametrices, show regularity with asymptotics of solutions in weighted edge spaces and illustrate the results by boundary-contact problems for the Laplacian with jumping coefficients.     

An inequality on the edge lengths of triangular meshes

We give a short proof of the following geometric inequality: for any two triangular meshes A and B of the same polygon C, if the number of vertices in A is at most the number of vertices in B, then the maximum length of an edge in A is at least the minimum distance between two vertices in B. Here the vertices in each triangular mesh include the vertices of the polygon and possibly additional Steiner points. The polygon must not be self-intersecting but may be non-convex and may even have holes. This inequality is useful for many purposes, especially in proving performance guarantees of mesh generation algorithms. For example, a weaker corollary of the inequality confirms a conjecture of Aurenhammer et al. [Theoretical Computer Science 289 (2002) 879-895] concerning triangular meshes of convex polygons, and improves the approximation ratios of their mesh generation algorithm for minimizing the maximum edge length and the maximum triangle perimeter of a triangular mesh.     

Algebraic convergence for anisotropic edge elements in polyhedral domains

We study approximation errors for the h-version of Nédélec edge elements on anisotropically refined meshes in polyhedra. Both tetrahedral and hexahedral elements are considered, and the emphasis is on obtaining optimal convergence rates in the H(curl) norm for higher order elements. Two types of estimates are presented: First, interpolation error estimates for functions in anisotropic weighted Sobolev spaces. Here we consider not only the H(curl)-conforming Nédélec elements, but also the H(div)-conforming Raviart-Thomas elements which appear naturally in the discrete version of the de Rham complex. Our technique is to transport error estimates from the reference element to the physical element via highly anisotropic coordinate transformations. Second, Galerkin error estimates for the standard H(curl) approximation of time harmonic Maxwell equations. Here we use the anisotropic weighted Sobolev regularity of the solution on domains with three-dimensional edges and corners. We also prove the discrete compactness property needed for the convergence of the Maxwell eigenvalue problem. Our results generalize those of [40] to the case of polyhedral corners and higher order elements.     

Strongly regular family of boundary-fitted tetrahedral meshes of bounded C2 domains

We give a constructive proof that for any bounded domain of the class C² there exists a strongly regular family of boundary-fitted tetrahedral meshes. We adopt a refinement technique introduced by K?í?ek and modify it so that a refined mesh is again boundary-fitted. An alternative regularity criterion based on similarity with the Sommerville tetrahedron is used and shown to be equivalent to other standard criteria. The sequence of regularities during the refinement process is estimated from below and shown to converge to a positive number by virtue of the convergence of q-Pochhammer symbol. The final result takes the form of an implication with an assumption that can be obviously fulfilled for any bounded C² domain.     

Mixed HP-finite element approximations on geometric edge and boundary layer meshes in three dimensions

Summary. In this paper, we consider the Stokes problem in a three-dimensional polyhedral domain discretized with hp finite elements of type ?^k for the velocity and ?^k?2 for the pressure, defined on hexahedral meshes anisotropically and non quasi-uniformly refined towards faces, edges, and corners. The inf-sup constant of the discretized problem is independent of arbitrarily large aspect ratios. Our work generalizes a recent result for two-dimensional problems in [10, 11].     

Least squares collocation solution of differential equations on irregularly shaped domains using orthogonal meshes

The least squares collocation (LESCO) method has been formulated to solve differential equations defined over irregular domains using a more convenient orthogonal computational mesh. The LESCO method is described in detail for second-order boundary value problems and applied to the time-dependent diffusion and advection-diffusion equations defined over two-dimensional irregular domains. Particular attention is given to the proper procedure for applying boundary conditions. Accuracy, convergence, and consistency are examined. For cubic elements with arbitrary location of collocation points, the convergence rate is between 3rd and 4th order. The major advantages of this method are reduced input data requirements, a more robust procedure for forming the equations, positive definite matrices, and flexibility in distrbuting errors.     

Generation of structured difference grids in two-dimensional nonconvex domains using mappings

Generation of structured difference grids in two-dimensional nonconvex domains is considered using a mapping of a parametric domain with a given nondegenerate grid onto a physical domain. For that purpose, a harmonic mapping is first used, which is a diffeomorphism under certain conditions due to Rado’s theorem. Although the harmonic mapping is a diffeomorphism, its discrete implementation can produce degenerate grids in nonconvex domains with highly curved boundaries. It is shown that the degeneration occurs due to approximation errors. To control the coordinate lines of the grid, an additional mapping is used and universal elliptic differential equations are solved. This makes it possible to generate a nondegenerate grid with cells of a prescribed shape.     

Robust intersection of structured hexahedral meshes and degenerate triangle meshes with volume fraction applications

Two methods for calculating the volume and surface area of the intersection between a triangle mesh and a rectangular hexahedron are presented. The main result is an exact method that calculates the polyhedron of intersection and thereafter the volume and surface area of the fraction of the hexahedral cell inside the mesh. The second method is approximate, and estimates the intersection by a least squares plane. While most previous publications focus on non-degenerate triangle meshes, we here extend the methods to handle geometric degeneracies. In particular, we focus on large-scale triangle overlaps, or double surfaces. It is a geometric degeneracy that can be hard to solve with existing mesh repair algorithms. There could also be situations in which it is desirable to keep the original triangle mesh unmodified. Alternative methods that solve the problem without altering the mesh are therefore presented. This is a step towards a method that calculates the solid area and volume fractions of a degenerate triangle mesh including overlapping triangles, overlapping meshes, hanging nodes, and gaps. Such triangle meshes are common in industrial applications. The methods are validated against three industrial test cases. The validation shows that the exact method handles all addressed geometric degeneracies, including double surfaces, small self-intersections, and split hexahedra.     

The optimal convergence of the h–p version of the boundary element method with quasiuniform meshes for elliptic problems on polygonal domains

In the framework of the Jacobi-weighted Besov spaces, we analyze the lower and upper bounds of errors in the h–p version of boundary element solutions on quasiuniform meshes for elliptic problems on polygons. Both lower bound and upper bound are optimal in h and p, and they are of the same order. The optimal convergence of the h–p version of boundary element method with quasiuniform meshes is proved, which includes the optimal rates for h version with quasiuniform meshes and the p version with quasiuniform degrees as two special cases. Dedicated to Professor Charles Micchelli on the occasion of his sixtieth birthday Mathematics subject classification (2000) 65N38. Benqi Guo: The work of this author was supported by NSERC of Canada under Grant OGP0046726 and was complete during visiting Newton Institute for Mathematical Sciences, Cambridge University for participating in special program “Computational Challenges in PDEs” in 2003. Norbert Heuer: This author is supported by Fondecyt project No. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis. Current address: Mathematical Sciences, Brunel University, Uxbridge, U.K.     

三维欧氏Steiner最小树的Delaunay四面体网格混合智能算法

Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。     

Elastic characteristics of ferrocement reinforced with woven meshes

Applying structural mechanics methods for composite materials, we have worked out a procedure for predicting the elasticity modulus, the shear modulus, and Poisson's ratio for ferrocement taking into account the elastic properties of the components, the wire diameter, the mesh size, and the distance between the meshes. The results make it possible to exploit the potential of such reinforcement to the fullest.Translated from Mekhanika Kompozitnykh Materialov, Vol. 30, No. 4, pp. 526–530, July–August, 1994.     

Angular Properties of Delaunay Diagrams in Any Dimension

Equiangularity (also called max-min angle criterion) is a well-known property of some planar triangulations that refine the Delaunay diagram. In this paper we generalize the notion of equiangularity to decompositions in inscribable polygons and we show that it characterizes the planar Delaunay diagram, even if more than three sites are cocircular. This result does not extend to higher dimensions. However, we characterize the Delaunay diagram in any dimension by a kind of dual property that we prove both with line angles and with solid angles. We also establish a local equiangularity of Delaunay diagrams in any dimension, and an angular characterization of self-centered diagrams. Finally, we show that these angular properties can, when appropriately defined, be generalized to the farthest point Delaunay diagram. Received April 25, 1996, and in revised form July 31, 1997, and March 18, 1998.     

Generalization and sharpening of Safta's Conjeture in the n-dimensional space

In this paper, a generalization and an improvement of Safta's conjecture in the n-dimensional space are given.     

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.