Quasi-triangulation and interworld data structure in three dimensions

It is well-known that the Voronoi diagram of points and the power diagram for weighted points, such as spheres, are cell complexes, and their respective dual structures, i.e. the Delaunay triangulation and the regular triangulation, are simplicial complexes. Hence, the topologies of these diagrams are usually stored in their dual complexes using a very compact data structure of arrays.The topology of the Voronoi diagram of three-dimensional spheres in the Euclidean distance metric, on the other hand, is stored in a radial edge data structure which is not as compact as the data structure used for the Voronoi diagram of points and the power diagram for weighted points.In this paper, we define a dual structure of the Voronoi diagram of three-dimensional spheres called a quasi-triangulation and present its important properties. Based on the properties of a quasi-triangulation, we propose a data structure, called an interworld data structure, based on arrays to compactly store the topology of the quasi-triangulation with a guaranteed query performance.     

Quasi-worlds and quasi-operators on quasi-triangulations

Quasi-triangulation is the dual structure of the Voronoi diagram of spheres, and it has been used as a convenient and powerful geometric construct for representing the proximity among spherical particles with different radii. In this paper, we present the formalism of the quasi-triangulation based on a quasi-world model and define primitive query operators called quasi-operators for correct and efficient topology traversal on the quasi-triangulation. Algorithms for the quasi-operators are also presented based on the extended inter-world data structure. The proposed quasi-operators have the potential to be a fundamental platform on which efficient algorithms for application problems on quasi-triangulation can be correctly and easily developed. The recently announced powerful constructs of the β-complex and the β-shape are such examples.     

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.     

Three-dimensional beta-shapes and beta-complexes via quasi-triangulation

The proximity and topology among particles are often the most important factor for understanding the spatial structure of particles. Reasoning the morphological structure of molecules and reconstructing a surface from a point set are examples where proximity among particles is important. Traditionally, the Voronoi diagram of points, the power diagram, the Delaunay triangulation, and the regular triangulation, etc. have been used for understanding proximity among particles. In this paper, we present the theory of the β-shape and the β-complex and the corresponding algorithms for reasoning proximity among a set of spherical particles, both using the quasi-triangulation which is the dual of the Voronoi diagram of spheres. Given the Voronoi diagram of spheres, we first transform the Voronoi diagram to the quasi-triangulation. Then, we compute some intervals called β-intervals for the singular, regular, and interior states of each simplex in the quasi-triangulation. From the sorted set of simplexes, the β-shape and the β-complex corresponding to a particular value of β can be found efficiently. Given the Voronoi diagram of spheres, the quasi-triangulation can be obtained in O(m) time in the worst case, where m represents the number of simplexes in the quasi-triangulation. Then, the β-intervals for all simplexes in the quasi-triangulation can also be computed in O(m) time in the worst case. After sorting the simplexes using the low bound values of the β-intervals of each simplex in O(mlogm) time, the β-shape and the β-complex can be computed in O(logm+k) time in the worst case by a binary search followed by a sequential search in the neighborhood, where k represents the number of simplexes in the β-shape or the β-complex. The presented theory of the β-shape and the β-complex will be equally useful for diverse areas such as structural biology, computer graphics, geometric modelling, computational geometry, CAD, physics, and chemistry, where the core hurdle lies in determining the proximity among spherical particles.     

Molecular surfaces on proteins via beta shapes

A protein consists of linearly combined amino acids via peptide bonds, and an amino acid consists of atoms. It is known that the geometric structure of a protein is the primary factor which determines the functions of the protein.Given the atomic complex of a protein, one of the most important geometric structures of a protein is its molecular surface since this distinguishes between the interior and exterior of the protein and plays an important role in protein folding, docking, interactions between proteins, and other functions.This paper presents an algorithm for the precise and efficient computation of the molecular surface of a protein, using a recently proposed geometric construct called the β-shape based on the Voronoi diagram of atoms in a protein. Given a Voronoi diagram of atoms, based on the Euclidean distance from the atom surfaces, the proposed algorithm first computes the β-shape with an appropriate sized probe. Then, the molecular surface is computed by employing a blending operation on the atomic complex of the protein. In this paper, it is also shown that for a given Voronoi diagram of atoms, the multiple molecular surfaces can be computed by using various sized probes.     

Three-dimensional beta shapes

The Voronoi diagram of a point set has been extensively used in various disciplines ever since it was first proposed. Its application realms have been even further extended to estimate the shape of point clouds when Edelsbrunner and Mücke introduced the concept of α-shape based on the Delaunay triangulation of a point set.In this paper, we present the theory of β-shape for a set of three-dimensional spheres as the generalization of the well-known α-shape for a set of points. The proposed β-shape fully accounts for the size differences among spheres and therefore it is more appropriate for the efficient and correct solution for applications in biological systems such as proteins.Once the Voronoi diagram of spheres is given, the corresponding β-shape can be efficiently constructed and various geometric computations on the sphere complex can be efficiently and correctly performed. It turns out that many important problems in biological systems such as proteins can be easily solved via the Voronoi diagram of atoms in proteins and β-shapes transformed from the Voronoi diagram.     

Power图的性质及构造算法研究

点集的Power图是点集Voronoi图的推广,特别适用用来解决涉及球（圆)的几何问题,文中首先对Power图的基本性质进行了几何化的证明;之后,研究了权为负数时对Power图的影响,指出在Power图的理论中允许权为负数,从而Power图可以应用到具有负权性质的领域;最后,给出了平面点集的Power图的构造算法,该算法到用Power图与正则三角化互为对偶的原理,在点集的正则三角化的基础上构造Power图,同时给出了实例以说明算法的有效性。     

基于MAC的ELF文件执行安全性的提高

随着Linux操作系统的应用与普及，其安全性也受到人们的广泛关注。在描述了消息鉴别码(MAC)计算和ELF文件格式之后，提出了保证ELF文件安全执行的方法，并对存在的问题进行了分析，给出了可行的解决办法。实验结果表明该方法是实际可行的。     

基于Voronoi图和GIS的设施区位配置研究

Voronoi图是一种基本的几何构造,是解决相关几何构造问题的有效工具.它正好满足了区位配置中设施定位求解中所遇到的一些问题.在讨论Voronoi图与区位配置模型的关系基础上,从设施配置应用需求的角度,总结与分析了Voronoi图的基本性质,着重介绍了基于Voronoi图的GIS区位配置方法与模型,并指出了进一步的研究与发展方向.     

Region-expansion for the Voronoi diagram of 3D spheres

Given a set of spheres in 3D, constructing its Voronoi diagram in Euclidean distance metric is not easy at all even though many mathematical properties of its structure are known. This Voronoi diagram has been known for many important applications from science and engineering. In this paper, we characterize the Voronoi diagram of spheres in three-dimensional Euclidean space, which is also known as an additively weighted Voronoi diagram, and propose an algorithm to construct the diagram. Starting with the ordinary Voronoi diagram of the centers of the spheres, the proposed region-expansion algorithm constructs the desired diagram by expanding the Voronoi region of each sphere, one after another. We also show that the whole Voronoi diagram of n spheres can be constructed in O(n³) time in the worst case.     

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, a similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a nondiscrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence. We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.     

Exploration of Empty Space among Spherical Obstacles via Additively Weighted Voronoi Diagram

Properties of granular materials or molecular structures are often studied on a simple geometric model – a set of 3D balls. If the balls simultaneously change in size by a constant speed, topological properties of the empty space outside all these balls may also change. Capturing the changes and their subsequent classification may reveal useful information about the model. This has already been solved for balls of the same size, but only an approximate solution has been reported for balls of different sizes. These solutions work on simplicial complexes derived from the dual structure of the ordinary Voronoi diagram of ball centers and use the mathematical concept of simplicial homology groups. If the balls have different radii, it is more appropriate to use the additively weighted Voronoi diagram (also known as the Apollonius diagram) instead of the ordinary diagram, but the dual structure is no longer a simplicial complex, so the previous approaches cannot be used directly. In this paper, a method is proposed to overcome this problem. The method works with Voronoi edges and vertices instead of the dual structure. Additional bridge edges are introduced to overcome disconnected cases. The output is a tree graph of events where cavities are created or merged during a simulated shrinking of the balls. This graph is then reorganized and filtered according to some criteria to get a more concise information about the development of the empty space in the model.     

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to improve their approximations. Voronoi diagrams turn out to be useful for this approximation. Although it is known that Voronoi vertices for a sample of points from a curve in 2D approximate its medial axis, a similar result does not hold in 3D. Recently, it has been discovered that only a subset of Voronoi vertices converge to the medial axis as sample density approaches infinity. However, most applications need a nondiscrete approximation as opposed to a discrete one. To date no known algorithm can compute this approximation straight from the Voronoi diagram with a guarantee of convergence. We present such an algorithm and its convergence analysis in this paper. One salient feature of the algorithm is that it is scale and density independent. Experimental results corroborate our theoretical claims.     

基于Voronoi图理论的自由边界型腔加工路径规划

Ｖｏｒｏｎｏｉ图是计算几何研究中的一个有力工具。给出了基于Ｖｏｒｏｎｏｉ图和单调区划分的型腔数控加工环切轨迹规划算法,并首次将其应用于边界为自由曲线的型腔,提高了Ｖｏｒｏｎｏｉ图在该领域的应用价值。     

Sorting helps for voronoi diagrams

It is well known that, using standard models of computation, Ω(n logn) time is required to build a Voronoi diagram forn point sites. This follows from the fact that a Voronoi diagram algorithm can be used to sort. However, if the sites are sorted before we start, can the Voronoi diagram be built any faster? We show that for certain interesting, although nonstandard, types of Voronoi diagrams, sorting helps. These nonstandard types of Voronoi diagrams use a convex distance function instead of the standard Euclidean distance. A convex distance function exists for any convex shape, but the distance functions based on polygons (especially triangles) lead to particularly efficient Voronoi diagram algorithms. Specifically, a Voronoi diagram using a convex distance function based on a triangle can be built inO (n log logn) time after initially sorting then sites twice. Convex distance functions based on other polygons require more initial sorting.     

Web数据库环境中分子结构式的处理

讨论了在Web数据库环境中处理分子结构式的问题。分子结构式可存储为静态图片格式或动态结构式格式。静态图片格式具有平台无关性,动态结构式格式则具有可编辑性及动态显示的优势。在关系数据库中,既可将分子式文件名或所在路径作为数据项,也可直接将分子式方 本身作为数据项。文中给出将分子式文件存入数据库的程序流程的示例,使用插件（Plug-in）或ActiveX控件,可在Web浏览器中直接显示动态的分子结构式,文中分析了二者处的优势,并结合ASP和Chime插件技术,给出了在数据库中检索分子结构式的具体实现方法。     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

Voronoi图在无线传感器网络栅栏覆盖中的应用研究*

Voronoi是计算几何学中的一个重要图结构,将其引入到无线传感器网络的覆盖控制中,特别是栅栏覆盖(barrier coverage)的研究中有着极其重要的指导意义.利用Voronoi图的划分,可快速搜索出传感器网络中的覆盖漏洞,在仅考虑邻近传感器节点影响的宽松覆盖要求下,论证出利用该图生成的最小暴露进攻轨迹逼近于理想情况;但由于Voronoi的划分仅仅是一种粗略的轨迹线段的集合,会造成该方法对网络拓扑情况相当敏感,这将一定程度上限制其应用范围.     

Voronoi图k阶邻近并行矩阵迭代算法

针对Voronoi图k阶邻近矢量法构建复杂发生元困难,栅格法耗时长、精度受限等问题,提出了一种基于矩阵迭代的并行计算方法。以刀片机作为并行计算的硬件平台,采用Arcgis软件将MapInfo格式矢量数据转换为栅格数据,实现了MPI并行环境中Voronoi图k阶邻近的栅格计算新方法。实验结果表明,改进后的Voronoi图k阶邻近栅格并行算法明显地提高了计算效率,且在栅格Voronoi图精度较高时,运行时间的拐点后移,加速比提高。