On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n²). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n).     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

The Properties of Voronoi Tessellations for 2D Ising Fluid Near the Second-Order Magnetic Phase Transition

The topological and geometrical properties of Voronoi cells generated for 2D fluid of hard disks with Ising-like spins near the second-order phase transition from the paramagnetic to ferromagnetic phase are described for different disk densities. The comparison with Voronoi cells generated for the random hard disk system is given.     

Effective atom volumes for implicit solvent models: comparison between Voronoi volumes and minimum fluctuation volumes

An essential element of implicit solvent models, such as the generalized Born method, is a knowledge of the volume associated with the individual atoms of the solute. Two approaches for determining atomic volumes for the generalized Born model are described; one is based on Voronoi polyhedra and the other, on minimizing the fluctuations in the overall volume of the solute. Volumes to be used with various parameter sets for protein and nucleic acids in the CHARMM force field are determined from a large set of known structures. The volumes resulting from the two different approaches are compared with respect to various parameters, including the size and solvent accessibility of the structures from which they are determined. The question of whether to include hydrogens in the atomic representation of the solute volume is examined. Copyright 2001 John Wiley & Sons, Inc. J Comput Chem 22: 1857-1879, 2001     

基于Voronoi切割算法的碎冰区构造及离散元分析

离散元方法广泛应用于海冰,特别是碎冰区的动力过程及其对海洋结构作用过程的数值模拟。为构造碎冰区中的冰块几何特性,基于二维Voronoi图方法对计算域进行随机切割以生成碎冰区中冰块的几何形态,并采用球体单元对每个碎冰块单元进行填充,从而确定碎冰区的初始分布场。在采用Voronoi图进行碎冰区构造时,可对冰块尺寸、几何形态和密集度等海冰参数进行设定。为确定冰块的不同几何规则度,综合采用排斥法和扰动法以定量地控制碎冰块几何形态从完全随机分布到规则分布的连续变换。为分析不同几何规则度下碎冰块的几何特性概率分布规律,对计算域内冰块的面积和边数等参数进行统计分析,从而可更合理地参数化控制初始冰场中碎冰块的几何特性。在此基础上,本文基于粘接-破碎的球体离散元方法对不同冰况下锥体结构的冰荷载进行了数值计算,讨论分析了碎冰区的海冰密集度、冰块面积和几何规则度对冰载荷的影响。     

双重点最小二乘配点无网格法

配点类无网格法需要计算近似函数的二阶导数,因而在移动最小二乘(MLS)近似中至少要采用二次基函数。本文利用Voronoi图对双重点移动最小二乘近似法进行了改进,建立了基于Voronoi图的双重点移动最小二乘近似(VDG),并利用加权最小二乘法离散微分方程,导出了双重点最小二乘配点无网格法(MD GLS)。该方法将求解域用节点离散,并以节点为生成点建立Voronoi图,取Voronoi多边形的顶点为辅助点。近似函数及其二阶导数的计算过程可分解为两个步骤:首先用场函数节点值拟合辅助点处近似函数的一阶导数,再以辅助点处近似函数的一阶导数值拟合节点处近似函数的二阶导数。由于在每一步中只需计算MLS形函数及其一阶导数,这种近似方法需要较少的影响点和较小的影响域。同时借助于Voronoi结构的优良几何性质,可以快速地搜索影响点。研究表明,与基于MLS的加权最小二乘无网格法(MWLS)相比,这种方法可以显著提高计算效率,并且在精度和收敛性方面也有所改善。     

Dislocation density crystalline plasticity modeling of lath martensitic microstructures in steel alloys

A three-dimensional multiple-slip dislocation density-based crystalline formulation, specialized finite-element formulations and Voronoi tessellations adapted to martensitic orientations were used to investigate large strain inelastic deformation modes and dislocation density evolution in martensitic microstructures. The formulation is based on accounting for variant morphologies and orientations, retained austenite and initial dislocation densities that are uniquely inherent to martensitic microstructures. The effects of parent austenite orientation and retained austenite were also investigated for heterogeneous fcc/bcc crystalline structures. Furthermore, the formulation was used to investigate microstructures mapped directly from SEM/EBSD images of martensitic steel alloys. The analysis indicates that variant morphology and orientations have a direct effect on dislocation density accumulation and inelastic localization in martensitic microstructures, and that lath directions, orientations and arrangements are critical characteristics of high strength martensitic deformation and behavior.     

On the Volume of Flowers in Space Forms

Let f(x ₁,..., x _N ) be a lattice polynomial in N variables, in which each variable occurs exactly once, B ₁,..., B _N be smoothly moving balls in the hyperbolic, Euclidean, or spherical space. Introducing a suitable modification of the Dirichlet–Voronoi decomposition, we prove a formula for the derivative of the volume of the domain f(B ₁,..., B _N ). As an application of the formula, we show that the volume increases if the balls move continuously in such a way that the functions _ij d _ij increase for all 1 i < j N, where _ij is a sign depending on f, d _ij is the distance between the centers of B _I and B _j .     

Numerical simulations of the steady Navier–Stokes equations using adaptive meshing schemes

In this paper, we consider an adaptive meshing scheme for solution of the steady incompressible Navier–Stokes equations by finite element discretization. The mesh refinement and optimization are performed based on an algorithm that combines the so‐called conforming centroidal Voronoi Delaunay triangulations (CfCVDTs) and residual‐type local a posteriori error estimators. Numerical experiments in the two‐dimensional space for various examples are presented with quadratic finite elements used for the velocity field and linear finite elements for the pressure. The results show that our meshing scheme can equally distribute the errors over all elements in some optimal way and keep the triangles very well shaped as well at all levels of refinement. In addition, the convergence rates achieved are close to the best obtainable. Extension of this approach to three‐dimensional cases is also discussed and the main challenge is the efficient implementation of three‐dimensional CfCVDT generation that is still under development. Copyright © 2007 John Wiley & Sons, Ltd.