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.     

Routing multiterminal nets on a hexagonal grid

Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19].     

Automatic parallel generation of tetrahedral grids by using a domain decomposition approach

An algorithm for the automatic parallel generation of three-dimensional unstructured grids based on geometric domain decomposition is proposed. A software package based on this algorithm is described. Examples of generating meshes for some application problems on a multiprocessor computer are presented. It is shown that the parallel algorithm can significantly (by a factor of several tens) reduce the mesh generation time. Moreover, it can easily generate meshes with as many as 5 × 10⁷ elements, which can hardly be generated sequentially. Issues concerning the speedup and the improvement of the efficiency of the computations and of the quality of the resulting meshes are discussed.     

Computing the face lattice of a polytope from its vertex-facet incidences

We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertex-facet incidences in time O(min{n,m}··), where n is the number of vertices, m is the number of facets, is the number of vertex-facet incidences, and  is the total number of faces of P. This improves results of Fukuda and Rosta [Computational Geometry 4 (4) (1994) 191–198], who described an algorithm for enumerating all faces of a d-polytope in O(min{n,m}·d·²) steps. For simple or simplicial d-polytopes our algorithm can be specialized to run in time O(d··). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.     

Adaptation and optimization of basic operations for an unstructured mesh CFD algorithm for computation on massively parallel accelerators

The design of efficient algorithms for large-scale gas dynamics computations with hybrid (heterogeneous) computing systems whose high performance relies on massively parallel accelerators is addressed. A high-order accurate finite volume algorithm with polynomial reconstruction on unstructured hybrid meshes is used to compute compressible gas flows in domains of complex geometry. The basic operations of the algorithm are implemented in detail for massively parallel accelerators, including AMD and NVIDIA graphics processing units (GPUs). Major optimization approaches and a computation transfer technique are covered. The underlying programming tool is the Open Computing Language (OpenCL) standard, which performs on accelerators of various architectures, both existing and emerging.     

Art gallery problem with guards whose range of vision is 180

It is shown that in any polygonal art gallery of n sides it is possible to place n/3 point guards whose range of vision is 180° so that every interior point of the gallery can be seen by at least one of them. The guards can be stationed at any point of the art gallery. This settles an open problem posed by J. Urrutia.     

The heat equation to generate planar grids

An algorithm for the generation of quadrilateral grids on planar domains is presented. This algorithm is given by an iterative procedure, where, starting from an initial grid on the domain under consideration, the coordinates of the grid vertices are iteratively adjusted by using a local discrete variational approach. This procedure resembles the explicit difference scheme for a perturbed heat equation, where the perturbation can be dropped for convex domains. Experimental results on benchmark domains are presented, and show an interesting behavior of the proposed method.     

Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns

Two-staged patterns are often used in manufacturing industries to divide stock plates into rectangular items. A heuristic algorithm is presented to solve the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. It uses the column-generation method to solve the residual problems repeatedly, until the demands of all items are satisfied. Each pattern is generated using a procedure for the constrained single large object placement problem to guarantee the convergence of the algorithm. The computational results of benchmark and practical instances indicate the following: (1) the algorithm can solve most instances to optimality, with the gap to optimality being at most one plate for those solutions whose optimality is not proven and (2) for the instances tested, the algorithm is more efficient (on average) in reducing the number of plates used than a published algorithm and a commercial stock cutting software package.     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

Combining Metaheuristics and Exact Methods for Solving Exactly Multi-objective Problems on the Grid

This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics – a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method – a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models – the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a bi-objective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem – 50 jobs on 5 machines. More than 400 processors belonging to 4 different administrative domains have contributed to the resolution process during more than 6 days.      

Algorithm for generating a conformal quasi-hierarchical triangular mesh that weakly δ-approximates given polygonal lines

An algorithm is proposed for generating a conformal quasi-hierarchical triangular mesh that approximates a set of given polygonal lines to accuracy δ. The solvability of the problem is guaranteed by the possibility of shifting the polygonal lines within their δ-neighborhood. The resulting mesh consists of a small number of triangles and admits a multigrid implementation. An estimate is given for the growing number of mesh triangles with decreasing δ (of order log ₂ ² δ^?1). The algorithm is applied to a particular set of polygonal lines.     

Rotationally optimal spanning and Steiner trees in uniform orientation metrics

We consider the problem of finding a minimum spanning and Steiner tree for a set of n points in the plane where the orientations of edge segments are restricted to λ uniformly distributed orientations, λ=2,3,4,… , and where the coordinate system can be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when λ=2 or λ=4. In the former, so-called rectilinear case, the edge segments have to be parallel to one of the coordinate axes, and in the latter, so-called octilinear case, the edge segments have to be parallel to one of the coordinate axes or to one of the lines making 45° with the coordinate axes (so-called diagonals). As the coordinate system is rotated—while the points remain stationary—the length and indeed the topology of the minimum spanning or Steiner tree changes. We suggest a straightforward polynomial-time algorithm to solve the rotational minimum spanning tree problem. We also give a simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting, and a finite time algorithm for the general Steiner tree problem with λ uniform orientations. Finally, we provide some computational results indicating the average savings for different values of n and λ both for spanning and Steiner trees.     

An effective hybrid algorithm for computing symbolic determinants

A hybrid algorithm for computing the determinant of a matrix whose entries are polynomials is presented. It is based on the dimension-decreasing algorithm [22] and the parallel algorithm for computing a symbolic determinant of [19]. First, through the dimension-decreasing algorithm, a given multivariate matrix can be converted to a bivariate matrix. Then, the parallel algorithm can be applied to effectively compute the determinant of the bivariate matrix. Experimental results show that the new algorithm can not only reduce enormously the intermediate expression swell in the process of symbolic computation, but also achieve higher degree of parallelism, compared with the single parallel algorithm given in [19].     

Tiling space and slabs with acute tetrahedra

We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 74.21°, and another which tiles a slab in space.     

A parallel algorithm for discrete least squares rational approximation

Summary A new method for discrete least squares linearized rational approximation is presented. It generalizes the algorithm of Rutishauser-Gragg-Harrod-Reichel for discrete least squares polynomial approximation to the rational case. The algorithm is fast in the sense that it requires orderm computation time wherem is the number of data points and is the degree of the approximant. We describe how this algorithm can be implemented in parallel.     

On 2D structured mesh generation by using mappings

A grid generation problem in two‐dimensional domains is considered by using a quasi‐conformal mapping of the parametric domain with a given square mesh onto the physical domain where the grid is required. To this end, a harmonic mapping is first applied, which, by the Radó theorem, is a diffeomorphism subject to some known conditions. However, the discrete harmonic mapping may produce folded meshes on a nonconvex domain with a strongly bent boundary. We demonstrate that it is caused by the truncation error. With the aim of controlling grid node location, an additional mapping is used. The Dirichlet problem for the universal elliptic partial differential equations is solved to construct the mapping. This allows to produce unfolded grids with a prescribed cell shape. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1072–1091, 2011     

Multi-stage scenario generation by the combined moment matching and scenario reduction method

We describe an opportunity to speed up multi-stage scenario generation and reduction using a combination of two well-known methods: the moment matching method (Høyland and Wallace, 2001) and the method for scenario reduction to approximately minimize a metric (Heitsch and Römish, 2009). Our suggestion is to combine them rather than using them in serial by making use of a stage-wise approximation to the moment matching algorithm. Computational results show that combining the methods can bring significant benefits.     

Parallel Metaheuristics for Workforce Planning

Workforce planning is an important activity that enables organizations to determine the workforce needed for continued success. A workforce planning problem is a very complex task requiring modern techniques to be solved adequately. In this work, we describe the development of three parallel metaheuristic methods, a parallel genetic algorithm, a parallel scatter search, and a parallel hybrid genetic algorithm, which can find high-quality solutions to 20 different problem instances. Our experiments show that parallel versions do not only allow to reduce the execution time but they also improve the solution quality.      

An adaptive strategy for elliptic problems including a posteriori controlled boundary approximation

We derive a posteriori error estimates for the approximation of linear elliptic problems on domains with piecewise smooth boundary. The numerical solution is assumed to be defined on a Finite Element mesh, whose boundary vertices are located on the boundary of the continuous problem. No assumption is made on a geometrically fitting shape.

A posteriori error estimates are given in the energy norm and the -norm, and efficiency of the adaptive algorithm is proved in the case of a saturated boundary approximation. Furthermore, a strategy is presented to compute the effect of the non-discretized part of the domain on the error starting from a coarse mesh. This especially implies that parts of the domain, where the measured error is small, stay non-discretized. The presented algorithm includes a stable path following to supply a sufficient polygonal approximation of the boundary, the reliable computation of the a posteriori estimates and a mesh adaptation based on Delaunay techniques. Numerical examples illustrate that errors outside the initial discretization will be detected.