AN 0 (N log N) HEURISTIC ALGORITHM FOR THE RECTILINEAR STEINER MINIMAL TREE PROBLEM

This paper presents an 0 (n log n) heuristic algorithm for the Rectilinear Steiner Minimal Tree (RSMT) problem. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the L₁ Delaunay triangulation, then constructs the Steiner minimal tree according to the properties of the Voronoi diagram and the Minimum Spanning Tree (MST) of the point set. The algorithm was implemented in FORTRAN-IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the 0 (n log n) algorithms with 0 (n₄) algorithms indicates that the 0 (n log n) algorithm achieves equally good reductions over the MST although the 0 (n₄) algorithms actually examine more potential Steiner points and RSMT configurations.     

Variational Delaunay approach to the generation of tetrahedral finite element meshes

We describe an algorithm which generates tetrahedral decomposition of a general solid body, whose surface is given as a collection of triangular facets. The principal idea is to modify the constraints in such a way as to make them appear in an unconstrained triangulation of the vertex set à priori. The vertex set positions are randomized to guarantee existence of a unique triangulation which satisfies the Delaunay empty‐sphere property. (Algorithms for robust, parallelized construction of such triangulations are available.) In order to make the boundary of the solid appear as a collection of tetrahedral faces, we iterate two operations, edge flip and edge split with the insertion of additional vertex, until all of the boundary facets are present in the tetrahedral mesh. The outcome of the vertex insertion is another triangulation of the input surfaces, but one which is represented as a subset of the tetrahedral faces. To determine if a constraining facet is present in the unconstrained Delaunay triangulation of the current vertex set, we use the results of Rajan which re‐formulate Delaunay triangulation as a linear programming problem. Copyright © 2001 John Wiley & Sons, Ltd.     

‘Ultimate’ robustness in meshing an arbitrary polyhedron

Given a boundary surface mesh (a set of triangular facets) of a polyhedron, the problem of deciding whether or not a triangulation exists is reported to be NP‐hard. In this paper, an algorithm to triangulate a general polyhedron is presented which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning, and a final phase that makes it possible to remove the additional points defined in the previous step. Following this phase, the resulting mesh conforms to the given boundary surface mesh. The proposed method results in a discussion of theoretical interest about existence and complexity issues. In practice, however, the method should provide what we call ‘ultimate’ robustness in mesh generation methods. Copyright © 2003 John Wiley & Sons, Ltd.     

The boundary recovery and sliver elimination algorithms of three‐dimensional constrained Delaunay triangulation

A boundary recovery and sliver elimination algorithm of the three‐dimensional constrained Delaunay triangulation is proposed for finite element mesh generation. The boundary recovery algorithm includes two main procedures: geometrical recovery procedure and topological recovery procedure. Combining the advantages of the edges/faces swappings algorithm and edges/faces splittings algorithm presented respectively by George and Weatherill, the geometrical recovery procedure can recover the missing boundaries and guarantee the geometry conformity by introducing fewer Steiner points. The topological recovery procedure includes two phases: ‘dressing wound’ and smoothing, which will overcome topology inconsistency between 3D domain boundary triangles and the volume mesh. In order to solve the problem of sliver elements in the three‐dimensional Delaunay triangulation, a method named sliver decomposition is proposed. By extending the algorithm proposed by Canvendish, the presented method deals with sliver elements by using local decomposition or mergence operation. In this way, sliver elements could be eliminated thoroughly and the mesh quality could be improved in great deal. Copyright © 2006 John Wiley & Sons, Ltd.     

Fast and robust Delaunay tessellation in periodic domains

An algorithm is presented for constructing three‐dimensional Delaunay tessellations in periodic domains. Applications include mesh generation for periodic transport problems and geometric decomposition for modelling particulate structures. The algorithm is a point insertion technique, and although the general framework is similar to point insertion in a convex hull, a number of new issues are introduced by periodicity. These issues are discussed in detail in the context of the computational algorithm. Examples are given for the tessellation of random points and random sphere packings. Performance data for the algorithm are also presented. These data show an empirical scaling of the computation time with size of O(N^1.11) and tessellation rates of 7000–14000 tetrahedrons per second for the problems studied (up to 10⁵ points). A breakdown of the performance is given, which shows the computational load is shared most heavily by two specific parts of the point‐insertion procedure. Copyright © 2002 John Wiley & Sons, Ltd.     

QuickTrace: a fast algorithm to detect contact

QuickTrace is a new, fast contact detection algorithm. It searches for contact typically between a tool, modelled by some kind of geometrical surface facets, and deforming material. Contact is searched for at material surface points called contact nodes. A contact node is in contact with a facet when the contact node is inside of the tool and the negative outer normal on the material surface at the contact node ‘leaves’ the tool surface through that facet. When multiple facets are intersected, only the closest facet to the contact node should be considered. From this definition of contact, the penetration depth results automatically as a by‐product. In QuickTrace, the m facets of the tool are packaged in boxes that are hierarchically ordered in a search tree with an average depth of log₄ m. The computational complexity for one contact search is proportional to this average depth. So, for n contact nodes the computational complexity is O(n log₄ m). This places QuickTrace amongst the best performing contact detection algorithms. At the same time there are no approximations or tricks involved and the contact detection is absolutely correct. The algorithm can easily be extended to material–material or tool–tool contact. Copyright © 2002 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation using Delaunay refinement with non‐standard quality measures

This paper studies the practical performance of Delaunay refinement tetrahedral mesh generation algorithms. By using non‐standard quality measures to drive refinement, we show that sliver tetrahedra can be eliminated from constrained Delaunay tetrahedralizations solely by refinement. Despite the fact that quality guarantees cannot be proven, the algorithm can consistently generate meshes with dihedral angles between 18^circ and 154^°. Using a fairer quality measure targeting every type of bad tetrahedron, dihedral angles between 14^° and 154^° can be obtained. The number of vertices inserted to achieve quality meshes is comparable to that needed when driving refinement with the standard circumradius‐to‐shortest‐edge ratio. We also study the use of mesh improvement techniques on Delaunay refined meshes and observe that the minimum dihedral angle can generally be pushed above 20^°, regardless of the quality measure used to drive refinement. The algorithm presented in this paper can accept geometric domains whose boundaries are piecewise smooth. Copyright © 2011 John Wiley & Sons, Ltd.     

The construction of improved‐quality mesh on a curved surface using mapping factors

Abstract

The Delaunay triangulation is broadly used on flat surfaces to generate well‐shaped elements. But the properties of Delaunay triangulation do not exist on curved surfaces whose Jacobians are different. In this paper we will present a modified algorithm to improve the shape of triangulation for the curved surface. The experiment results show that making use of “mapping factors” in the Delaunay triangulation and Laplacian method can produce better mesh (most aspect ratios≤3) on a curved surface.     

Accuracy of Galerkin finite elements for groundwater flow simulations in two and three‐dimensional triangulations

In standard finite element simulations of groundwater flow the correspondence between hydraulic head gradients and groundwater fluxes is represented by the stiffness matrix. In two‐dimensional problems the use of linear triangular elements on Delaunay triangulations guarantees a stiffness matrix of type M. This implies that the local numerical fluxes are physically consistent with Darcy's law. This condition is fundamental to avoid the occurrence of local maxima or minima, and is of crucial importance when the calculated flow field is used in contaminant transport simulations or pathline evaluation. In three spatial dimensions, the linear Galerkin approach on tetrahedra does not lead to M‐matrices even on Delaunay meshes. By interpretation of the Galerkin approach as a subdomain collocation scheme, we develop a new approach (OSC, orthogonal subdomain collocation) that is shown to produce M‐matrices in three‐dimensional Delaunay triangulations. In case of heterogeneous and anisotropic coefficients, extra mesh properties required for M‐stiffness matrices will also be discussed. Copyright © 2001 John Wiley & Sons, Ltd.     

An L∞–Lp mesh‐adaptive method for computing unsteady bi‐fluid flows

This paper discusses the contribution of mesh adaptation to high‐order convergence of unsteady multi‐fluid flow simulations on complex geometries. The mesh adaptation relies on a metric‐based method controlling the L ^p‐norm of the interpolation error and on a mesh generation algorithm based on an anisotropic Delaunay kernel. The mesh‐adaptive time advancing is achieved, thanks to a transient fixed‐point algorithm to predict the solution evolution coupled with a metric intersection in the time procedure. In the time direction, we enforce the equidistribution of the error, i.e. the error minimization in L ^∞ norm. This adaptive approach is applied to an incompressible Navier–Stokes model combined with a level set formulation discretized on triangular and tetrahedral meshes. Applications to interface flows under gravity are performed to evaluate the performance of this method for this class of discontinuous flows. Copyright © 2010 John Wiley & Sons, Ltd.     

OPTIMAL DELAUNAY POINT INSERTION

An efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in ℝ³ with a linear generation rate of 15 000 tetrahedra per second for randomly generated points on an HP 735 workstation.     

A two‐level nonoverlapping Schwarz algorithm for the Stokes problem without primal pressure unknowns

A two‐level nonoverlapping Schwarz algorithm is developed for the Stokes problem. The main feature of the algorithm is that a mixed problem with both velocity and pressure unknowns is solved with a balancing domain decomposition by constraints (BDDC)‐type preconditioner, which consists of solving local Stokes problems and one global coarse problem related to only primal velocity unknowns. Our preconditioner allows to use a smaller set of primal velocity unknowns than other BDDC preconditioners without much concern on certain flux conditions on the subdomain boundaries and the inf–sup stability of the coarse problem. In the two‐dimensional case, velocity unknowns at subdomain corners are selected as the primal unknowns. In addition to them, averages of each velocity component across common faces are employed as the primal unknowns for the three‐dimensional case. By using its close connection to the Dual–primal finite element tearing and interconnecting (FETI‐DP algorithm) (SIAM J Sci Comput 2010; 32 : 3301–3322; SIAM J Numer Anal 2010; 47 : 4142–4162], it is shown that the resulting matrix of our algorithm has the same eigenvalues as the FETI‐DP algorithm except zero and one. The maximum eigenvalue is determined by H/h, the number of elements across each subdomains, and the minimum eigenvalue is bounded below by a constant, which does not depend on any mesh parameters. Convergence of the method is analyzed and numerical results are included. Copyright © 2011 John Wiley & Sons, Ltd.     

H 8 fuzzy control for time‐delay affine Takagi‐Sugeno fuzzy models: An ILMI approach

Abstract

This paper deals with the fuzzy based H₈ control problem for time‐delay affine Takagi‐Sugeno (T‐S) fuzzy models. A class of nonlinear time‐delay systems is approximated by a time‐delay affine T‐S fuzzy model in this paper. Based on Lyapunov‐Razumikhin theorem and S‐procedure, the stability and stabilization problems are solved by employing a Parallel Distributed Compensation (PDC) type H₈ fuzzy controller. The synthesis for the time‐delay affine T‐S fuzzy models is a Bilinear Matrix Inequality (BMI) problem and it can not be solved via a convex optimization algorithm. Hence, an Iterative Linear Matrix Inequality (ILMI) algorithm is used to solve the BMI problems in this paper. Finally, a numerical simulation for a delayed pendulum system is given to show the applications of the present approach.     

STEINER PROBLEMS IN GRAPHS: ALGORITHMS AND APPLICATIONS

Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ? V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.     

Adaptive tetrahedral mesh generation by constrained Delaunay refinement

This paper presents a tetrahedral mesh generation method for numerically solving partial differential equations using finite element or finite volume methods in three‐dimensional space. The main issues are the mesh quality and mesh size, which directly affect the accuracy of the numerical solution and the computational cost. Two basic problems need to be resolved, namely boundary conformity and field points distribution. The proposed method utilizes a special three‐dimensional triangulation, so‐called constrained Delaunay tetrahedralization to conform the domain boundary and create field points simultaneously. Good quality tetrahedra and graded mesh size can be theoretically guaranteed for a large class of mesh domains. In addition, an isotropic size field associated with the numerical solution can be supplied; the field points will then be distributed according to it. Good mesh size conformity can be achieved for smooth sizing informations. The proposed method has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance. Copyright © 2008 John Wiley & Sons, Ltd.     

Using a genetic algorithm to generate D‐optimal designs for mixture‐process variable experiments

This article presents and develops a genetic algorithm (GA) to generate D‐efficient designs for mixture‐process variable experiments. It is assumed the levels of a process variable are controlled during the process. The GA approach searches design points from a set of possible points over a continuous region and works without having a finite user‐defined candidate set. We compare the performance of designs generated by the GA with designs generated by two exchange algorithms (DETMAX and k‐exchange) in terms of D‐efficiencies and fraction of design space (FDS) plots which are used to evaluate a design's prediction variance properties. To illustrate the methodology, examples involving three and four mixture components and one process variable are proposed for creating the optimal designs. The results show that GA designs have superior prediction variance properties in comparison with the DETMAX and k‐exchange algorithm designs when the design space is the simplex or is a highly‐constrained subspace of the simplex.     

Organizing distributed data bases for parallel searching

Abstract

This paper is mainly concerned with the problem of distributing a data base (i.e., a set of segments) in a computer network system so as to facilitate parallel searching. In our distributed data base model, we assume that all segments are stored in nodes. Each time a query occurs, all nodes are searched concurrently. For convenience, we define the time required to access a segment from any node as a time unit. For a network with d nodes, the response time of a query is then identical to the maximum (n ₁ , n ₂, …, n_d ), where n_i , is the number of segments that satisfies the query and is stored in node i. Unfortunately, the solution for finding an optimal way to organize a distributed data base for parallel searching is still at large. In other words, given a data base, there is no efficient polynomial time algorithm for finding an optimal arrangement of segments onto nodes. In this article, we shall present a “heuristic algorithm” based upon a multivariant analysis method in statistics to distribute a data base in a network system. Some experimental results will show that our method is indeed feasible and effective.     

广义欧几里德Steiner问题的研究与进展

广义欧几里德Steiner问题足指确定连接平面上一组给定点的满足特定连通性要求的最短网络的问题。本文主要介绍了比问题的研究与进展,在建立了求给定平面点集的最矩U-连通(或边连通)生成网络的整数规划模型的基础上,证明了文献[13]中所给的一个例子是错误的,并提出了一些关于广义Steiner问题的进一步研究的问题。     

Nondestructive identification of multiple flaws using XFEM and a topologically adapting artificial bee colony algorithm

We present a novel algorithm based on the extended finite element method (XFEM) and an enhanced artificial bee colony (EABC) algorithm to detect and quantify multiple flaws in structures. The concept is based on recent work that have shown the excellent synergy between XFEM, used to model the forward problem, and a genetic‐type algorithm to solve an inverse identification problem and converge to the ‘best’ flaw parameters. In this paper, an adaptive algorithm that can detect multiple flaws without any knowledge on the number of flaws beforehand is proposed. The algorithm is based on the introduction of topological variables into the search space, used to adaptively activate/deactivate flaws during run time until convergence is reached. The identification is based on a limited number of strain sensors assumed to be attached to the structure surface boundaries. Each flaw is approximated by a circular void with the following three variables: center coordinates (x_c, y_c) and radius (r_c), within the XFEM framework. In addition, the proposed EABC scheme is improved by a guided‐to‐best solution updating strategy and a local search (LS) operator of the Nelder–Mead simplex type that show fast convergence and superior global/LS abilities compared with the standard ABC or classic genetic algorithms. Several numerical examples, with increasing level of difficulty, are studied in order to evaluate the proposed algorithm. In particular, we consider identification of multiple flaws with unknown a priori information on the number of flaws (which makes the inverse problem harder), the proximity of flaws, flaws having irregular shapes (similar to artificial noise), and the effect of structured/unstructured meshes. The results show that the proposed XFEM–EABC algorithm is able to converge on all test problems and accurately identify flaws. Hence, this methodology is found to be robust and efficient for nondestructive detection and quantification of multiple flaws in structures. Copyright © 2013 John Wiley & Sons, Ltd.     

Constrained boundary recovery for three dimensional Delaunay triangulations

A new constrained boundary recovery method for three dimensional Delaunay triangulations is presented. It successfully resolves the difficulties related to the minimal addition of Steiner points and their good placement. Applications to full mesh generation are discussed and numerical examples are provided to illustrate the effectiveness of guaranteed recovery procedure. Copyright © 2004 John Wiley & Sons, Ltd.