Numerical simulation of two-dimensional soap froth

The temporal evolution of two-dimensional foam is studied by event-driven numerical simulations based on different types of models. It is shown that most of the dynamical and topological features seen in experimental measurements can be reproduced. The average area of cells scales linearly with time and the distribution of n-sided cells can be compared with known results. The topological models regarding the lengths of the boundaries yield the best results among the models studied.     

Optimal approximation and quantisation

A number of interesting functionals F(X) of a finite point set X in the Euclidean space can be represented as integrals of a function η that depends on the integration variable y and X restricted onto a certain set C(y,X) that is determined by y and X and satisfies separation and uniform boundedness conditions. For instance, C(y,X) can be the Voronoi cell generated by X that contains y. We single out the general properties of C and η that ensure that the normalised infimum of F(X) over all sets X with cardinality n converges to a limit that can be identified using a particular form of η. The considered functionals include those that appear in quantisation problems for probability measures, and in finding the optimal approximation of a function by splines, tangent planes and triangulated surfaces. For instance, it is shown that the minimum Lβ-approximation error (normalised by nβ) of a sufficiently smooth bivariate convex function f using the convex triangulation converges to the L1/(β+1)-norm of the determinant of the second derivative of f times a certain absolute constant.     

Computing reconstructions from nonuniform Fourier samples: Universality of stability barriers and stable sampling rates

We study the problem of recovering an unknown compactly-supported multivariate function from samples of its Fourier transform that are acquired nonuniformly, i.e. not necessarily on a uniform Cartesian grid. Reconstruction problems of this kind arise in various imaging applications, where Fourier samples are taken along radial lines or spirals for example.Specifically, we consider finite-dimensional reconstructions, where a limited number of samples is available, and investigate the rate of convergence of such approximate solutions and their numerical stability. We show that the proportion of Fourier samples that allow for stable approximations of a given numerical accuracy is independent of the specific sampling geometry and is therefore universal for different sampling scenarios. This allows us to relate both sufficient and necessary conditions for different sampling setups and to exploit several results that were previously available only for very specific sampling geometries.The results are obtained by developing: (i) a transference argument for different measures of the concentration of the Fourier transform and Fourier samples; (ii) frame bounds valid up to the critical sampling density, which depend explicitly on the sampling set and the spectrum.As an application, we identify sufficient and necessary conditions for stable and accurate reconstruction of algebraic polynomials or wavelet coefficients from nonuniform Fourier data.     

基于k-fold交叉验证的代理模型序列采样方法

在代理模型序列采样框架下,针对现有研究中的不足之处,通过引入k-fold交叉验证计算样本的预测误差,并结合泰森多边形法和最大距离最小化准则,发展了一种适用于任意代理模型的k-fold CV-Voronoi自适应序列采样方法。相较于传统序列采样方法,本文方法具有计算简单和自适应性强等显著优势。通过数值算例和工程算例对比分析发现所提序列采样方法具有较高的近似精度和计算效率,此外,进一步讨论了k-fold交叉验证中k的不同取值对于代理模型精度的影响,总结出k的最优取值范围以供参考。     

Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay

In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.

     

Conservative semi‐Lagrangian advection on adaptive unstructured meshes

A conservative semi‐Lagrangian method is designed in order to solve linear advection equations in two space variables. The advection scheme works with finite volumes on an unstructured mesh, which is given by a Voronoi diagram. Moreover, the mesh is subject to adaptive modifications during the simulation, which serves to effectively combine good approximation quality with small computational costs. The required adaption rules for the refinement and the coarsening of the mesh rely on a customized error indicator. The implementation of boundary conditions is addressed. Numerical results finally confirm the good performance of the proposed conservative and adaptive advection scheme. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 388–411, 2004     

Realistic nano-polycrystalline microstructures: beyond the classical Voronoi tessellation

A modified Voronoi tessellation (MVT) is proposed for the computer simulation of realistic microstructures. Compared with standard tessellations, the present algorithm provides the desired grain size distribution in a one-step, non-evolutionary procedure. This is obtained by relaxing the constraints of Voronoi tessellation on position and orientation of the grain boundaries, with the only side effect being the formation of a limited amount of eliminable voids. As an example, it is shown how to directly obtain a distribution of grains of given variance and with a shape statistically close to the lognormal one.     

三维自然单元法插值形函数的导数计算

根据Voronoi胞的几何性质,获得了积分点的二阶Voronoi胞顶点的表达式,并对各邻近结点相关的顶点进行排序以使其生成的二阶Voronoi胞切割面为凸多边形,从而获得各切割凸多边形面域的面积表达式;最后,基于复合函数链式求导法则,获得了三维自然单元法non-Sibson插值形函数导数的显式格式。相比Lasserre算法,该方法具有直观、便于编程且计算量小的特点。悬臂梁的算例结果进一步说明了该方法的可靠性,证实了文献[2,7,8]关于自然单元法具有比有限元中常应变单元更高的精度,理论上和双线性单元的精度同阶的结论。     

基于Voronoi图盲区的无线传感器网络覆盖控制部署策略

针对无线传感器网络在二维平面应用场景中的覆盖控制问题, 提出了一种基于泰森盲区多边形形心的覆盖控制部署策略(blind-zone centroid-based scheme, BCBS). BCBS先对监测区域做Voronoi图划分以得到被每个传感器节点覆盖的泰森多边形, 而后根据泰森多边形顶点的覆盖情况分析得出泰森多边形内的盲区, 并构造与盲区形状相近的多边形, 最后以该多边形的几何中心作为传感器节点移动的候选目标位置, 从而达到提高网络覆盖率的目的. 仿真实验结果表明, BCBS在覆盖率、节点分布均匀性与节点覆盖效率等方面相比CBS有明显优势. 关键词： 无线传感器网络 节点覆盖 Voronoi图 多边形形心     

A Voronoi‐based ALE solver for the calculation of incompressible flow on deforming unstructured meshes

An Arbitrary Lagrangian–Eulerian method for the calculation of incompressible Navier–Stokes equations in deforming geometries is described. The mesh node connectivity is defined by a Delaunay triangulation of the nodes, whereas the discretized equations are solved using finite volumes defined by the Voronoi dual of the triangulation. For prescribed boundary motion, an automatic node motion algorithm provides smooth motion of the interior nodes. Changes in the connectivity of the nodes are made through the use of local transformations to maintain the mesh as Delaunay. This allows the nodes and their associated Voronoi finite volumes to migrate through the domain in a free manner, without compromising the quality of the mesh. An MAC finite volume solver is applied on the Voronoi dual using a cell‐centred non‐staggered formulation, with cell‐face velocities being calculated by the Rhie–Chow momentum interpolation. Advective fluxes are approximated with the third‐order QUICK differencing scheme. The solver is demonstrated via its application to a driven cavity flow, and the flow about flapping aerofoil geometries. Copyright © 2010 John Wiley & Sons, Ltd.