Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

Non-zero boundaries of Leibniz half-spaces

It is proved that for any , there exists a norm and two points , in such that the boundary of the Leibniz half-space has non-zero Lebesgue measure. When , it is known that the boundary must have zero Lebesgue measure.

     

Towards a Characterization of Self-Similar Tilings in Terms of Derived Voronoï Tessellations

In this paper, a technique for analyzing levels of hierarchy in a tiling of Euclidean space is presented. Fixing a central configuration P of tiles in , a `derived Voronoï' tessellation _P is constructed based on the locations of copies of P in . A family of derived Voronoï tilings is formed by allowing the central configurations to vary through an infinite number of possibilities. The family will normally be an infinite one, but we show that for a self-similar tiling it is finite up to similarity. In addition, we show that if the family is finite up to similarity, then is pseudo-self-similar. The relationship between self-similarity and pseudo-self-similarity is not well understood, and this is the obstruction to a complete characterization of self-similarity via our method. A discussion and conjecture on the connection between the two forms of hierarchy for tilings is provided.     

Improving continuity of Voronoi-based interpolation over Delaunay spheres

There are two types of the discontinuity of the original Voronoi-based interpolants: one appears on the data sites and the other on the Delaunay spheres. Some techniques are known for reducing the first type of the discontinuity, but not for the second type. This is mainly because the second type of the discontinuity comes from the coordinate systems used for the interpolants. This paper proposes a sequence of new coordinate systems, called the kth-order standard coordinates, for all nonnegative integers k, and shows that the interpolant generated by the kth-order standard coordinates have C^k continuity on the Delaunay spheres. The previously known Voronoi-based interpolants coincide with the cases k=0 and k=1. Hence, the standard coordinate systems constructed in this paper can reduce the second type of the discontinuity as much as we want. In addition, this paper derives a formula for the gradient of the standard coordinates.     

A natural neighbour method based on Fraeijs de Veubeke variational principle for materially non-linear problems

Abstract The natural neighbour method can be considered as one of many variants of the meshless methods. In the present paper, a new approach based on the Fraeijs de Veubeke （FdV） functional, which is initially developed for linear elasticity, is extended to the case of geometrically linear but materially non-linear solids. The new approach provides an original treatment to two classical problems： the numerical evaluation of the integrals over the domain A and the enforcement of boundary conditions of the type ui = hi on Su. In the absence of body forces （Fi = 0）, it will be shown that the calculation of integrals of the type fA .dA can be avoided and that boundary conditions of the type ui = hi on Su can be imposed in the average sense in general and exactly if hi is linear between two contour nodes, which is obviously the case for tTi = O.     

A novel mesh-free poly-cell Galerkin method

A novel numerical method is explored and named as mesh-free poly-cell Galerkin method. An improved moving least-square （MLS） scheme is presented, which can avoid the matrix inversion in standard MLS and can be used to construct shape functions possessing delta Kronecher property. A new type of local support is introduced to ensure the alignment of integral domains with the cells of the back-ground mesh, which will reduce the difficult in integration. An intensive numerical study is conducted to test the accuracy of the present method. It is observed that solutions with good accuracy can be obtained with the present method.     

Numerical simulation of thermo-mechanical fatigue properties for particulate reinforced composites

In this paper, a two dimensional Voronoi cell element, formulated with creep, thermal and plastic strain, is applied for the numerical simulation of thermo-mechanical fatigue behavior for particulate reinforced composites. The relation between mechanical fatigue phases and thermal fatigue phases influences the thermo-mechanical fatigue behavior and cyclic creep damage. The topological features of micro-structure in particulate reinforced composites, such as the orientation, depth-width ratio, distribution and volume fraction of inclusions, have a great influence on thermo-mechanical behavior. Some related conclusions are obtained by examples of numerical simulation.The project supported by the Special Funds for the National Major Fundamental Research Projects (2004CB619304), the National Natural Science Foundation of China (10276020 and 50371042), the Key Grant Project of Chinese Ministry of Education (0306)     

Proposal of FEM implemented with particle discretization for analysis of failure phenomena

A new method for numerical simulation of failure behavior, namely, FEM-β, is proposed. For a continuum model of a deformable body, FEM-β solves a boundary value problem by applying particle discretization to a displacement field; the domain is decomposed into a set of Voronoi blocks and the non-overlapping characteristic functions for the Voronoi blocks are used to discretize the displacement function. By computing average strain and average strain energy, FEM-β obtains a numerical solution of the variational problem that is transformed from the boundary value problem. In a rigorous form, FEM-β is formulated for a variational problem of displacement and stress with different particle discretization, i.e., the non-overlapping characteristic function of the Voronoi blocks and the conjugate Delaunay tessellations, respectively, are used to discretize the displacement and stress functions. While a displacement field is discretized with non-smooth functions, it is shown that a solution of FEM-β has the same accuracy as that of ordinary FEM with triangular elements. The key point of FEM-β is the ease of expressing failure as separation of two adjacent Voronoi blocks owing to the particle discretization that uses non-overlapping characteristic functions. This paper explains these features of FEM-β with results of numerical simulation of several example problems.     

基于Voronoi cells的二维不规则自适应网格的生成及其应用

基于Voronoi cells的数据结构和算法，给出了一种二维不规则自适应网格的生成方法，用VisualC＋＋语言在微机上开发了Windows环境下网格自动生成的可视化软件。既可以得到Voronoi cells网格，也可得到相应的Delaunay triangles网格，网格生成的实例表明，本文方法所得到的网格非常适合于多尺度系统的流动问题的计算，具有较好的应用前景。