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     

How disorder can diminish avalanche risks: effect of size distribution

We study the behavior of disk assemblies with a variable disorder distribution. The packing is first consolidated and then continuously tilted very slowly. The amount of displaced disks for each tilted angle is recorded. Large displacements of the disks can occur due to some local or global mechanical instabilities. The definition of neighboring disks is based on radical (extension of Voronoï) tessellation rules to decompose, in a unique and perfectly defined manner, the two-dimensional space for polydisperse disks. In this way, by comparing the characteristics of stability for one disk to the neighboring ones for local ordered cluster, we can predict the global amount of displaced disks. Some tilting cycles have been performed to check the correlation between the instability of the packing structure (collective displacements) with micro and macro order parameters.     

无线传感网络覆盖中概率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.     

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

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

基于Voronoi图和复合泊松过程的WSN覆盖算法设计

设计了一种基于Voronoi图和复合泊松过程的分布式算法。利用Voronoi图的性质,传感器节点能够同时进行冗余判定和感知半径调节来消除覆盖冗余;利用休眠节点的复合泊松探测过程,能够及时发现工作节点的失效并弥补网络的覆盖漏洞,使网络由单纯的完成监测任务变为动态调整拓扑以适应环境变化。仿真结果表明网络能准确调度节点状态,并且对工作节点失效具有很好的鲁棒性。     

Feature-Adaptive Rendering of Loop Subdivision Surfaces on Modern GPUs

We present a novel approach for real-time rendering Loop subdivision surfaces on modern graphics hardware. Our algorithm evaluates both positions and normals accurately, thus providing the true Loop subdivision surface. The core idea is to recursively refine irregular patches using a GPU compute kernel. All generated regular patches are then directly evaluated and rendered using tile hardware tessellation unit. Our approach handles triangular control meshes of arbitrary topologies and incorporates common subdivision surface features such as semi-sharp creases and hierarchical edits. While surface rendering is accurate up to machine precision, we also enforce a consistent bitwise evaluation of positions and normals at patch boundaries. This is particularly useful in the context of displacement mapping which strictly requires inatching surface normals. Furthermore, we incorporate efficient level-of-detail rendering where subdivision depth and tessellation density can be adjusted on-the-fly. Overall, our algorithm provides high-quality results at real-time frame rates, thus being ideally suited to interactive rendering applications such as video games or authoring tools.     

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.