Delaunay Triangulation (delaunay + triangulation)

Distribution by Scientific Domains


Selected Abstracts


Parallel divide-and-conquer scheme for 2D Delaunay triangulation

CONCURRENCY AND COMPUTATION: PRACTICE & EXPERIENCE, Issue 12 2006
Min-Bin Chen
Abstract This work describes a parallel divide-and-conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub-block triangulations are merged. Finding the affected zone can reduce the amount of data required to be transmitted between processors. The time complexity of the divide-and-conquer scheme remains O(n log n), and the affected region can be located in O(n) time steps, where n denotes the number of points. The code was implemented with C, FORTRAN and MPI, making it portable to many computer systems. Experimental results on an IBM SP2 show that a parallel efficiency of 44,95% for general distributions can be attained on a 16-node distributed memory system. Copyright 2006 John Wiley & Sons, Ltd. [source]


Geometry update driven by material forces for simulation of brittle crack growth in functionally graded materials

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, Issue 13 2009
Rolf Mahnken
Abstract Functionally graded materials (FGMs) are advanced materials that possess continuously graded properties, such that the growth of cracks is strongly dependent on the gradation of the material. In this work a thermodynamic consistent framework for crack propagation in FGMs is presented, by applying a dissipation inequality to a time-dependent migrating control volume. The direction of crack growth is obtained in terms of material forces as a result of the principle of maximum dissipation. In the numerical implementation a staggered algorithm,deformation update for fixed geometry followed by geometry update for fixed deformation,is employed within each time increment. The geometry update is a result of the incremental crack propagation, which is driven by material forces. The corresponding mesh is generated by combining Delaunay triangulation with local mesh refinement. Furthermore a Newton algorithm is proposed, taking into account mesh transfer of displacements for crack propagation in incremental elasticity. In two numerical examples brittle crack propagation in FGMs is investigated for various directions of strength gradation within the structures. Copyright 2008 John Wiley & Sons, Ltd. [source]


Local maximum-entropy approximation schemes: a seamless bridge between finite elements and meshfree methods

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, Issue 13 2006
M. Arroyo
Abstract We present a one-parameter family of approximation schemes, which we refer to as local maximum-entropy approximation schemes, that bridges continuously two important limits: Delaunay triangulation and maximum-entropy (max-ent) statistical inference. Local max-ent approximation schemes represent a compromise,in the sense of Pareto optimality,between the competing objectives of unbiased statistical inference from the nodal data and the definition of local shape functions of least width. Local max-ent approximation schemes are entirely defined by the node set and the domain of analysis, and the shape functions are positive, interpolate affine functions exactly, and have a weak Kronecker-delta property at the boundary. Local max-ent approximation may be regarded as a regularization, or thermalization, of Delaunay triangulation which effectively resolves the degenerate cases resulting from the lack or uniqueness of the triangulation. Local max-ent approximation schemes can be taken as a convenient basis for the numerical solution of PDEs in the style of meshfree Galerkin methods. In test cases characterized by smooth solutions we find that the accuracy of local max-ent approximation schemes is vastly superior to that of finite elements. Copyright 2005 John Wiley & Sons, Ltd. [source]


Automatic construction of non-obtuse boundary and/or interface Delaunay triangulations for control volume methods

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, Issue 7 2002
Nancy Hitschfeld
Abstract A Delaunay mesh without triangles having obtuse angles opposite to boundary and interface edges (obtuse boundary/interface triangles) is the basic requirement for problems solved using the control volume method. In this paper we discuss postprocess algorithms that allow the elimination of obtuse boundary/interface triangles of any constrained Delaunay triangulation with minimum angle ,. This is performed by the Delaunay insertion of a finite number of boundary and/or interface points. Techniques for the elimination of two kinds of obtuse boundary/interface triangles are discussed in detail: 1-edge obtuse triangles, which have a boundary/interface (constrained) longest edge; and 2-edge obtuse triangles, which have both their longest and second longest edge over the boundary/interface. More complex patterns of obtuse boundary/interface triangles, namely chains of 2-edge constrained triangles forming a saw diagram and clusters of triangles that have constrained edges sharing a common vertex are managed by using a generalization of the above techniques. Examples of the use of these techniques for semiconductor device applications and a discussion on their generalization to 3-dimensions (3D) are also included. Copyright 2002 John Wiley & Sons, Ltd. [source]


Efficient Delaunay-based localized routing for wireless sensor networks

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 7 2007
Yu Wang
Abstract Consider a wireless sensor network consisting of n wireless sensors randomly distributed in a two-dimensional plane. In this paper, we show that with high probability we can locally find a path for any pair of sensors such that the length of the path is no more than a constant factor of the minimum. By assuming each sensor knows its position, our new routing method decides where to forward the message purely based on the position of current node, its neighbours, and the positions of the source and the target. Our method is based on a novel structure called localized Delaunay triangulation and a geometric routing method that guarantees that the distance travelled by the packets is no more than a small constant factor of the minimum when the Delaunay triangulation of sensor nodes are known. Our experiments show that the delivery rates of existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies, and our localized routing protocol based on Delaunay triangulation works well in practice. We also conducted extensive simulations of another localized routing protocol, face routing. The path found by this protocol is also reasonably good compared with previous one although it cannot guarantee a constant approximation on the length of the path travelled theoretically. Copyright 2006 John Wiley & Sons, Ltd. [source]


Parallel Delaunay mesh generation kernel

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, Issue 2 2003
Nikos Chrisochoides
Abstract We present the results of an evaluation study on the re-structuring of a latency-bound mesh generation algorithm into a latency-tolerant parallel kernel. We use concurrency at a fine-grain level to tolerate long, variable, and unpredictable latencies of remote data gather operations required for parallel guaranteed quality Delaunay triangulations. Our performance data from a 16 node SP2 and 32 node Cluster of Sparc Workstations suggest that more than 90% of the latency from remote data gather operations can be masked effectively at the cost of increasing communication overhead between 2 and 20% of the total run time. Despite the increase in the communication overhead the latency-tolerant mesh generation kernel we present in this paper can generate tetrahedral meshes for parallel field solvers eight to nine times faster than the traditional approach. Copyright 2003 John Wiley & Sons, Ltd. [source]


Automatic construction of non-obtuse boundary and/or interface Delaunay triangulations for control volume methods

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, Issue 7 2002
Nancy Hitschfeld
Abstract A Delaunay mesh without triangles having obtuse angles opposite to boundary and interface edges (obtuse boundary/interface triangles) is the basic requirement for problems solved using the control volume method. In this paper we discuss postprocess algorithms that allow the elimination of obtuse boundary/interface triangles of any constrained Delaunay triangulation with minimum angle ,. This is performed by the Delaunay insertion of a finite number of boundary and/or interface points. Techniques for the elimination of two kinds of obtuse boundary/interface triangles are discussed in detail: 1-edge obtuse triangles, which have a boundary/interface (constrained) longest edge; and 2-edge obtuse triangles, which have both their longest and second longest edge over the boundary/interface. More complex patterns of obtuse boundary/interface triangles, namely chains of 2-edge constrained triangles forming a saw diagram and clusters of triangles that have constrained edges sharing a common vertex are managed by using a generalization of the above techniques. Examples of the use of these techniques for semiconductor device applications and a discussion on their generalization to 3-dimensions (3D) are also included. Copyright 2002 John Wiley & Sons, Ltd. [source]


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

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, Issue 4 2001
Christian Cordes
Abstract 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. [source]