Ready, Set, Go! The Voronoi diagram of moving points that start from a line

It is an outstanding open problem of computational geometry to prove a near-quadratic upper bound on the number of combinatorial changes in the Voronoi diagram of points moving at a common constant speed along linear trajectories in the plane. In this note we observe that this quantity is Θ(n²) if the points start their movement from a common line.     

Polygonal extrusion

A sweeping operation called polygonal extrusion is defined to improve the modeling power of CSG-based modeling. It is assumed that a 2D cross-sectional polygon (sweeping polygon) moves in space while its containing plane is kept orthogonal to the tangent direction of the trajectory curve, a planar polygonal chain having no self-intersections. The objective of the paper is to compute the boundary of the swept volume of the sweeping polygon as a set of polygons (or triangles). The most significant challenge to accomplishing this objective is the problem of trimming the swept volume. To solve the trimming problem, 2D-curve offsetting methods are employed. Two algorithms are presented for polygonal extrusion that are based on different offsetting methods, the Voronoi diagram and PWID offset. The proposed algorithms have been implemented and tested with various examples. Published online: 28 January 2003     

无线传感网络覆盖中概率Voronoi模型及算法研究

覆盖是无线传感网络中最重要的问题之一,随机覆盖是目前研究的主流。基于Voronoi图的随机覆盖算法是无线传感网络领域的研究热点。目前研究中采用的Voronoi图,主要采用基于距离的Voronoi边赋权值模型,存在两个主要问题,即模型粗糙和监测节点不全。以实测的分段概率传感模型为基础,从多传感协同监测的角度构造一种概率Voronoi模型,试图解决以上问题。并且用基于概率Voronoi模型的最大突破路径算法验证了模型有效性。就掌握的文献来看,该模型是首次提出,具有较好的实用推广价值。     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

Simulation of polycrystalline aluminum tensile test with crystal plasticity finite element method

The crystal plasticity was implemented in the finite element method（FEM） software ABAQUS through the user subroutine UMAT. By means of discretizing the space at the grain level with the Voronoi diagram method, a polycrystal model was built and used in the FEM analysis. The initial orientation of each grain was generated based on the orientation distribution function（ODF）. The developed model was successfully applied in simulation of polycrystalline aluminium samples deformed by the tensile tests. The theoretical strain--stress relation was in good agreement with the experimental result. The simulation results show that the grain size has significant effect on the deformation behavior. The initial plastic deformation usually occurs at grain boundaries, and multiple slip often results in an enhanced local hardening at grain boundaries.     

热成形过程微观组织模拟研究进展

金属在热成形过程中微观组织发生诸如晶粒长大、再结晶等一系列的复杂变化,会直接影响加工过程与产品的力学性能。对近年计算机技术在热成形微观组织演变模拟方面的研究进展做了比较全面的评述,比较了相关的微观组织模拟方法,分析了利用各种模拟技术所取得的研究成果。     

An alignment-free fingerprint bio-cryptosystem based on modified Voronoi neighbor structures

Bio-cryptography is an emerging security technology which combines cryptography with biometrics. A good bio-cryptosystem is required to protect the privacy of the relevant biometric data as well as achieving high recognition accuracy. Fingerprints have been widely used in bio-cryptosystem design. However, fingerprint uncertainty caused by distortion and rotation during the image capturing process makes it difficult to achieve a high recognition rate in most bio-cryptographic systems. Moreover, most existing bio-cryptosystems rely on the accurate detection of singular points for fingerprint image pre-alignment, which is very hard to achieve, and the image rotation transformation during the alignment process can cause significant singular point deviation and minutiae changes. In this paper, by taking full advantage of local Voronoi neighbor structures (VNSs), e.g. local structural stability and distortion insensitivity, we propose an alignment-free bio-cryptosystem based on fixed-length bit-string representations extracted from modified VNSs, which are rotation- and translation-invariant and distortion robust. The proposed alignment-free bio-cryptosystem is able to provide strong security while achieving good recognition performance. Experimental results in comparison with most existing alignment-free bio-cryptosystems using the publicly-available databases show the validity of the proposed scheme.     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

动态受限区域内的单纯型连续近邻链查询方法

受限区域内的单纯型连续近邻链查询在空间数据挖掘、数据的相似分析和推理、空间数据库等方面具有重要的作用。为了弥补已有方法的不足,详细研究了动态受限区域内的单纯型连续近邻链查询方法。基于计算几何中的Voronoi图给出了VOR_IN_CRSCNNC算法、VOR_EX_CRSCNNC算法和VOR_DE_CRSCNNC算法。进一步进行了实验比较和分析。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一筛选和判断的冗余计算,在处理空间数据量较大、初始受限区域数据量较多、受限区域形状较为复杂的单纯型连续近邻链查询方面具有较大的优势。     

一种基于Voronoi图求解车辆路径问题的混合启发式算法

针对由多个配送中心和多个客户点组成的物流网络中的车辆路径问题,提出了一种基于“集群第一,路线第二”的路径优化策略,即首先使用Voronoi分割对配送区域进行划分,然后引入综合插入算法和变邻域搜索算法的混合启发式算法求解配送区域内车辆路径问题。通过算例和应用系统的分析与验证表明,该混合算法既能获取质量较优解,同时也具有较好的实时性,能较好地满足实际应用需求。