Voronoi图算法及其在混合电路的衬底耦合研究中？…

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行２,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图。在 计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题。算法时间复杂度为Ｏ（ｎｌｏｇｎ）空间复杂度为Ｏ（ｎ）。     

线段加权的Voronoi图

本文将点上加权的Ｖｏｒｏｎｏｉ图推广到线段上加权的Ｖｏｒｏｎｏｉ图，证明了该图的两线段间的Ｖｏｒｏｎｏｉ边是二次曲线，给出了所有情形下两线段间的Ｖｏｒｏｎｏｉ边的具体形状和画法及线段加权的Ｖｏｒｏｎｏｉ图Ｖｎ的画法。     

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

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

面条目标Voronoi图生成的动态距离变换策略

利用Ｖｅｃｔｏｒ－ｂａｓｅｄ方法生成的矢量Ｖｏｒｏｎｏｉ图用于ＧＩＳ有局限性,那么自然而然就会想到能否在栅格空间中生成栅格Ｖｏｒｏｎｏｉ图,与之对应的生成算法被称作Ｒａｓｔｉｒ－ｂａｓｉｄ方法。本文首先介绍了与Ｒａｓｔｅｒ－ｂａｓｅｄ方法有关的研究工作,在此基础上提出用传统的距离变换建立栅格Ｖｏｒｏｎｏｉ图,而后又指出这种方法建立Ｖｏｕｏｎｏｉ图引起的误差与距离成线性正比关系,为减小误差,作者提出     

一种基于图的平面点集Delaunay三角剖分算法

本文提出了一种基于图的平面点集Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出平面点集的欧几里得最小生成树，然后逐次加入一边构造三角形网格，最后按最小内角最大的三角化准则，通过局部变换，得到平面点集的Ｄｅｌａｕｎａｙ三角剖分。本文同时阐述了它的对偶图；平面点集的Ｖｏｒｏｎｏｉ图的概念和性质。     

最短路径重构算法

研究了在Ｎ个顶点的图中，仅给出了所有顶点对之间最短路径距离矩阵，而计算任两顶点间最短路径问题。这种算法因没有利用原始图中有关边的信息，被称为重构算法。本研究取得了如下成果：①在单一的顶点对之间最短路径重构的时间复杂度为Ｏ（ｎｌｏｇｎ）；②在所有顶点对之间的最短路径重构的时间复杂度为Ｏ（ｎ＾３）；③在带有ｎ／ｌｏｇｎ个处理器的独占读写并行随机访问器上，单一顶点对之间的最短路径重构时间复杂度为Ｏ（（ｌ     

完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

用O(tlogt)的连接图求有障碍时的最短路径

针对有障碍时求两点间的最短路径这一问题,提出了极区和自由区的概念,并由此构造出一种新的强连接图ＣＦ,它由自由区的特征边和障碍的极边构成,其顶点数为Ｏ（ｔ）,边数为Ｏ（ｔｌｏｇｔ）,其中ｔ为障碍的极边数,而现有最佳连通图的顶点数和边数为Ｏ（ｔ＾２）,同时提出了时间复杂度为Ｏ（ｔｌｏｇ＾２ｔ）的高效ＧＦ构造算法,并使用“不改向”的启发式Ａ算法在ＧＦ中寻找两点间的最短路径。     

基于Wormhole路由的二维Mesh上的并行k-选择

由于二维网孔机器的结构简单、规整,易于ＶＬＳＩ实现,使得它不仅成为许多理论研究的基础模型,而且还是许多并行机所采用的互连结构．Ｗｏｒｍ ｈｏｌｅ 路由技术的采用改进了二维网孔机器的通信能力．该文在带有Ｗｏｒｍ ｈｏｌｅ 路由技术的ｎ×ｎ 二维网孔机器上提出了一个时间复杂度为Ｏ（ｌｏｇ２ｎｌｏｇｌｏｇｎ）的并行ｋ－选择算法,改进了该问题在Ｓｔｏｒｅ－ａｎｄ－Ｆｏｒｗ ａｒｄ 路由技术下的时间复杂度下界Ｏ（ｎ）．据已掌握的资料,该算法为最早的、非总线连接的二维网孔机器上的、时间复杂度为对数的多项式级的ｋ－选择算法．     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．     

分区加权Voronoi图的性质及其面积计算

分区加权Voronoi图是Voronoi图和加权Voronoi图的推广,可以用来模拟移动通信中基站发射天线分扇区以不同功率向周围发射时所覆盖区域的形状。首先,给出了分区加权Voronoi图的性质、定理及相关证明;其次,分析了分区加权Voronoi图中的各种区域,并给出了一种计算相应区域面积的算法;最后,利用分区加权Voronoi图模拟石家庄市部分城区中的基站建设情况,并对模拟产生的重复覆盖、服务区和盲区面积进行了计算。     

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.     

带线段障碍的城市Voronoi图生成算法研究

带线段障碍的城市Voronoi图是城市Voronoi图的扩展.在步行或使用一般交通工具的情况下,客观世界中存在着许多不能逾越的障碍,甚至连交通网络也时常被一些障碍隔开.许多障碍可简化为线段障碍来处理.给出带线段障碍的城市Voronoi图的定义、性质,结晶生长算法和实例.算法简单,可扩展性好,具有较高的理论价值和应用价值.     

三维限定Voronoi网格剖分细化算法

针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段平面片分别进行一维二维Power图细化以实现三维限定Voronoi 网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.     

Euclidean Voronoi diagram of 3D balls and its computation via tracing edges

Despite its important applications in various disciplines in science and engineering, the Euclidean Voronoi diagram for spheres, also known as an additively weighted Voronoi diagram, in 3D space has not been studied as much as it deserves. In this paper, we present an algorithm to compute the Euclidean Voronoi diagram for 3D spheres with different radii. The presented algorithm follows Voronoi edges one by one until the construction is completed in O(mn) time in the worst-case, where m is the number of edges in the Voronoi diagram and n is the number of spherical balls. As building blocks, we show that Voronoi edges are conics that can be precisely represented as rational quadratic Bézier curves. We also discuss how to conveniently represent and process Voronoi faces which are hyperboloids of two sheets.     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

基链分治算法与Voronoi区的面积计算定理研究

基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时,在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法.     

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

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

Polyline‐sourced Geodesic Voronoi Diagrams on Triangle Meshes

This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N = max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm.     

Discrete Voronoi diagrams and the SKIZ operator: a dynamicalgorithm

The Voronoi diagram (VD) is a popular tool for partitioning the support of an image. An algorithm is presented for constructing VD when the seed set, which determines the Voronoi regions, can be modified by adding and removing seeds. The number of pixels and seeds revisited for updating the diagram and the neighbor relationships among seeds is minimized. A result on cocircular seeds is presented. The adjacency, or dual, graph of the VD is readily obtained. The use of the algorithm for constructing skeletons by influence zones (SKIZ) is demonstrated