R2中圆盘的Voronoi图、拟三角剖分和β-复合体的二维对应定义及其实现

计算设计与工程学报。号12（2014）79~87www.jcde.orgR2中圆盘的Voronoi图、拟三角剖分和β-复合体：理论和BetaConceptJae-Kwan Kim1，Youngsong Cho1，Donguk Kim2 and Deok-Soo Kim3，*1韩国首尔汉阳大学Voronoi图研究中心2韩国江原道江陵市江陵原州国立大学工业信息与管理工程系3韩国首尔汉阳大学机械工程系（2013年9月17日接收;2013年10月28日修订;2013年11月1日接受摘要Voronoi图是解决粒子间空间问题的有力工具，已被广泛应用于科学和工程领域特别是三维球体的Voronoi图，也称为加性加权Voronoi图，已经证明了它在解决分子生物学和材料科学中原子排列的空间推理问题方面的强大能力为了解决应用问题，对偶结构，称为准三角形，及其衍生结构，称为β-复形，经常与Voronoi图本身一起使用然而，Voronoi图，准三角测量和β-复合体有时被认为是普通用户难以理解的。本文给出了它们的二维对应定义，并介绍了实现这一理论的BetaConcept程序，使用户能在一个平面上容易地了解这些结构的强大概念和功能BetaConcept程序用标准C++语言和MFC及OpenGL实现，可在Voronoi Diagram Research Center（voronoi.hanyang.ac.kr）免费获得关键词：圆盘Voronoi图;加权Voronoi图;拟三角剖分; β-复合物; β-形状;球形原子; GUI程序1. 介绍Voronoi图是解决粒子间空间问题的有力工具[1]。三维球形原子的Voronoi图，又称加性加权Voronoi图，近年来在生物学和材料科学中显示出分析分子结构的强大能力然而，我们已经了解到，有些用户可能认为原子的Voronoi图，其对偶结构称为准三角形，以及β复合物有点难以理解。在本文中，我们介绍了它们的定义的二维对应物，并提出了BetaConcept程序，这是一个基于GUI的程序，用于R2中的Voronoi图，准三角剖分和beta复形，具有以下目标：1) 为了帮助用户更容易地理解Voronoi图、拟三角剖分和拟三角剖分的概念，*通讯作者。联系电话：+822-220-0472，传真：+82 2-292-0472电子邮件地址：dskim@hanyang.ac.kr© 2014 CAD/CAM工程师协会Techno-Press doi：10.7315/JCDE. 2014. 008R2中的ta-络合物，2) 帮 助 用 户 识 别 这 些 结 构 的 应 用 ， 并 在BetaConcept程序中进行测试（有许多重要的应用，如机器人路径规划、自动汽车导航等）。在R2中），并且3) 帮助用户扩展他们对R3 的理解，并鼓励使用BetaMol程序[2]，这是一个三维分子的分子建模，分析和可视化程序。4) 此外，本文还引入了两个形式化的定义：R2中Voronoi图与拟三角剖分之间的对偶映射和拟单纯复形的新概念，我们相信这两个概念将在未来的理论中发挥重要作用我 们 建 议 读 者 从 Voronoi Diagram Research Center（VDRC）（http：voronoi.hanyang.ac.kr）免费下载并测试 BetaCon- cept 程 序 。 本 文 中 的 所 有 图 形 均 由BetaConcept程序生成。本文的结构如下：第2，3，4节分别介绍了圆盘的Voronoi图、拟三角剖分和β-复形的理论;第5节介绍了BetaConcept程序;第6节总结了本文的研究结果。80J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）79~87本文2. 圆盘的Voronoi图设P ={p1，p2，...，pn}是R2中的点集. P的普通Voronoi图VD是空间的镶嵌，其中Voronoi单元VC（pi）是更接近pi的位置的集合而不是pj，ij。设A ={a1，a2，=（pi，ri），中心pi，半径ri在R2中。对于ai，V-胞元VC（ai）定义为VC（ai）={x∈R3| dist（x，pi）− ri ≤dist（x，pj）表示x，y∈R3之间的欧氏距离。然后，A的Voronoi图VD，也称为加法-加权Voronoi图定义为VD = {VC（a1），VC（a2），.，VC（an）}。VD中的顶点、边和单元之间的连通性由于其平面性而可以存储在诸如翼边或半边数据结构之类的数据结构中。BetaConcept程序采用了翼边数据结构。它与R3中球体的Voronoi图的对应物可以存储在径向边缘数据结构中[3]。VD由三元组（VV，EV，CV）表示，其中VV，EV和CV分别是Voronoi顶点（V-顶点）、Voronoi边（V-边）和Voronoi单元（V-单元）的集合关于VD在三维空间中的性质和算法的细节，见[4，5]。拓扑数据结构见[6]。关于圆盘的Voronoi图及其相关问题已有一些研究Lee和Drysdale考虑了一组不相交圆盘的Voronoi图问题，并提出了一个运行时间为O（nlog2n）的算法[7]。Sharir报告了一个算法计算一个磁盘集的Voronoi图，时间复杂度为O（nlog2n），其中磁盘可以相交[8]。Yap报告了一个O（nlogn）算法，用于计算由线段和圆弧组成的封闭多边形的Gavrilova和Rokne报告了一种算法，该算法在磁盘动态移动时保持有效的数据结构[10]。Sugihara利用普通Voronoi点图的面向拓扑的鲁棒计算的强大能力[11]报道了一种圆盘集的近似Kim等人开发了一种边缘翻转算法，该算法通过在最坏情况下在O（n2）时间内翻转点的普通Voronoi图的边缘来计算圆盘的Voronoi图为了用户的直观性和便于应用，我们更倾向于使用BetaConcept程序是基于Kim和同事对由普通Voronoi图计算的圆盘Voronoi图的边缘翻转算法图1（a）是点集P的普通Voronoi图VD，图1（b）是圆盘集A的Voronoi图VD，其中P中的每个点都有一个具有指定半径的相关圆形原子。注意，两个最大原子之间的微小原子具有仅由两个V边限定的V胞。我们称这个微小的原子与一个（一）（b）第（1）款（c）第（1）款图1.点与圆的Voronoi图：（a）点的Voronoi图VD，（b）圆的Voronoi图VD，（c）叠加。2-边有界V-胞腔图1（c）显示了VD和VD的叠加。检查VD和VD之间的相似性和不相似性：VD的边缘在VD中翻转。3. 拟三角剖分Voronoi图通常以其双重结构存储，从存储和查询过程的角度来看，这既方便又有效点的普通Voronoi图VD的对偶是Delaunay三角剖分DT，它是一个单纯复形。圆盘的Voronoi图VD的对偶结构称为准三角形QT，其通常可以是非单纯复形[14，15]。J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）78~8681定义1. 设D是一个对偶算子，R2中的VD到QT如下： D：cV 是一个从V-胞腔c V ∈CV到qt-顶点vQ∈ VQ。qt的坐标顶点vQ是圆盘a的中心p，到V-细胞cV。82J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）79~87我JK D：eV EeQ是从V-边eV∈EV到一个qt-边eQ∈EQ。qt边eQ是一条直线以vQi和vQj为界的线段，对于不同的i和j，其中圆盘ai和aj定义了V边eV。 D：vVfQ是从V-顶点vV∈VV一个qt-面fQ∈FQ。qt-面fQ是一个拓扑的由三个顶点vQ，vQ和vQ围成的三角形，对于不同的i，j和k，它们对应于定义V-顶点vV的三个圆盘。每对qt-顶点定义fQ的qt-边eQ。fQ的取向是关键的，并且应该与入射到vV的V边的角排序一致。图2示出了对偶映射D的示例。图2（b）中的qt-顶点vQ1、vQ2和vQ3是从图2（a）中的V-单元cV1、cV2和cV3变换而来的。因此，qt-顶点的坐标来自对应于V-单元的圆盘的中心的坐标。qt边eQ1、eQ2和eQ3分别来自V边eV1、eV2和eV3。qt面fQ1来自V顶点cV1。在映射D中，qt-边和qt-面的方向被小心地保持。从QT到VD的逆映射D−1也可以类似地定义。VD和QT之间的对偶映射D在某种程度上类似于VD和DT之间的对偶映射。简单地说，在平面中，D将V-单元映射到qt-顶点，将V-边映射到qt-边，（一）（b）第（1）款图2.对偶映射D如下：（a）三个圆的Voronoi图，（b）变换后的拟三角剖分。（一）（b）第（1）款（c）第（1）款J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）78~8683（d）其他事项图3. QT异常：（a）示意图异常 QT伴VD，（b）真实QT异常，（c）和（d）以嵌套形式发生的异常。84J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）79~87和一个v顶点到一个qt单元。然后，准三角剖分可以由三元组QT=（VQ，EQ，FQ）表示，其中VQ，EQ和FQ分别是顶点单形（qt-顶点），边单形（qt-边）和三角形单元单形因此，QT正确地定义了磁盘之间的接近度，从拓扑的角度来看，它等价于VD在最坏的情况下，VD可以在O（m）时间内转换为QT，其中m表示QT中的单形数。关于在更一般的三维空间中的拟三角剖分的详细定义和性质，参见[14，15]。众所周知，Delaunay三角形和正则三角形是一种单纯复形，它能很好地回答各种几何和拓扑问题。然而，早先观察到R3中的拟三角剖分具有违反单纯复形条件的性质[14，15]。到目前为止，复形只被认为是一般的非单纯复形，如果它不满足单纯复形的条件在本文中，我们提出了一个独特的非单纯复形，其定义如下：定义2. C是一个拟单纯复形，如果它满足以下两个条件： C中元素的任何面也在C中，并且 C中的两个元素相交于一个或多个低维面，如果它相交的话。要知道，这个定义是单纯复形的一个轻微的推广。C中的两个k-单形可以共享k+1个公共（k−1）-单形，其中k≤d。证明了拟三角剖分是一个拟单形复杂. 图3示出了一个示例。图3（a）示出了五个圆盘和Voronoi图VD（以实线示出）。绿色的虚线（有两条弯曲的曲线）表示VD的对偶映射的示意图，因此它们共同表示拟三角剖分QT的拓扑。请注意，每条绿色虚线对应于一条V形边，中间有两个三角形，由两个大圆盘和一个小圆盘图3（b）显示了通过拉直弯曲曲线获得的实际QT请注意，由绿色虚线边界定的两个示意性三角形不重叠，因此它们在拓扑上是不同的。然而，在图3（b）的QT中，这两个绿色的虚线三角形映射到两个看起来相同的瘦三角形（由绿色实线段限定）红色三角形表示这一事实，因此从几何角度来看，这意味着有两个重叠的三角形这种现象被称为异常。图3（c）和3（d）显示，这种异常可以以嵌套形式发生存储QT和VD的数据结构是重要的。虽然DT可以存储在单纯复杂数据结构（SCDS）中，但QT需要一种称为世界间数据结构（IWDS）的专门变体参见Kim等人。[14]了解R3中IWDS的详细信息。然而，有趣的是，在R2中，IWDS减少到SCDS。从拓扑学的角度看，R2中QT和DT的区别在于：在DT中，两个三角形面最多可以共享一条边，而在QT中，两个三角形面可以共享一条或两条边。QT的这个属性可以被合并到SCDS中，因为两个入射面指针具有相同的值。图4（a）和4（b）分别显示了用于Voronoi图的（标准全）翼边数据结构和BetaConcept程序中准三角测量的世界间数据结构箭头旁边的整数表示指针的数量。如果查询仅用于单形之间的拓扑遍历，则图4（b）中的数据结构可以进一步简化为图4（c）。BetaConcept显式地表示边单形。请注意，图4（c）中的模式也是存储Delaunay三角剖分拓扑图5示出了对应于图1（b）中的Voronoi图注意在两个最大的圆盘之间有一个红色的三角形这个看似一个三角形实际上是两个三角形的叠加：一个是从Voronoi图中两个最大圆盘之间的Voronoi边上的两个Voronoi顶点中的每一个进行在这种情况下，一个三角形是顺时针的(a)（b）（c）图4.数据结构模式：（a）用于VD的翼边数据结构（WEDS），（b）用于QT的世界间数据结构（IWDS），（c）IWDS的压缩版本。J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）78~8685图5.图1（b）中的Voronoi图的准三角剖分。定向（具有负符号区域），而另一个是逆时针定向（具有正符号区域）。红色三角形对应于带负符号区域的三角形。这个有趣的情况被称为异常情况，是平面上唯一的一个异常情况。在三维情况下，还有其他异常情况，详情见[16]。4. β-络合物假设我们从QT中选择一条qt边e（连接一对原子中心），并考虑半径为β的圆形探针。假设我们在两个原子周围移动探针，并测试探针是否可以在两个原子之间自由移动而不同时与两个原子相交。如果探针可以通过，我们从QT中移除e。否则，我们就把它留在QT。我们对QT中的所有qt边重复此操作。现在，我们从QT中选择一个qt-胞元f（连接三个原子中心）。我们检查是否有可能将探针放置在三个原子之间，以便它可以同时与所有三个原子如果可以放置，我们从QT中删除qt单元。否则，我们将qt单元格留在QT中。我们还对QT中的所有qt-单元格重复此操作。然后，我们剩下QT的一个子集，它对应于一个称为β复合体BC的对象，该对象对应于探针。因此，β复合体是准三角测量的子集，其中其边界由探针的大小定义（即，探针半径）。由β-复合物的边界约束的空间的区域被称为β-形状BS。关于R3的详细信息，请参见[17]。上面的描述告诉我们，从拟三角剖分中提取β复形实际上是一个寻找合适的单形的问题。如果按照如下所述的状态对单形进行分类，并使用指示探测半径范围的参数进行排序，则可以有效地进行该搜索假设σ是qt边。然后，如果探针可以在恰好两个位置处接触σ，则σ被称为奇异的;如果探针只能在单个位置处接触σ，则σ被称为正则的;如果探针不能接触σ，则σ被称为内部的;否则（即，探针可自由通过σ），σ为外部。假设σ是qt-顶点。然后，如果接触σ的探针中心的轨迹是一个完整的圆，则σ是奇异的，并且如果表1.二维拟三角剖分中单形β-区间的计算规则单形 和他们的当地居民规则边界状态奇异定期内部三角脸1[ρ，∞）边缘无接头SH（A），unattached2[ρ，μ][μm，μm][μm，∞）附件SH（A）3[μm，μm][μm，∞）∈ SH（A），无连接4[ρ，μ][μm，∞）∈ SH（A），附5[μm，∞）顶点中国（A）6[-∞，μm）[μm，μm][μm，∞）∈ SH（A）7[-∞，μm） [μm，∞）轨迹是一个或多个弧。在所有情况下，如果探针不能在任何位置接触σ，则σ是内部的一个qt-顶点永远不会是外部的。假设σ是qt-面。那么，如果探针不能放置在三个圆盘的中间，除非它与一个或多个圆盘相交，则σ是内部的否则，σ是外部的。表1总结了用于基于单形的状态从准三角剖分中提取β复形的详细搜索规则BetaConcept程序中采用了图4（b）的世界间数据结构模式，因为应该显式表示边单形以存储每个边的间隔（称为beta间隔）。有关规则的详细信息，请参见[17]。关于R3中的inter-world数据结构，参见[14]。在最坏的情况下，β-复形的单纯形搜索可以在O（logm）时间内完成，其中m是准三角形中的单纯形的数量[17]。单纯形搜索的计算问题在[18]中针对一般查询进行了讨论图6（a）示出了输入圆盘生成器和准三角剖分。图6（b）至图6（f）是从小数值到无穷大尺寸增加的各种探针图6（c）显示了准三角测量中的异常三角形没有出现，而图6（d）显示了当探针尺寸稍微增加时，异常三角形（瘦红色面）记住，红色三角形的面实际上是两个三角形。图6（f）是对应于无限大的探针尺寸的β复合体，并且与准三角测量相同假设我们收集beta复合体边界上的顶点和边，并认为边界的内部填充有材料。然后，填充对象因此是β形状并且具有以下属性：i）它可以由多边形组成，其内部被填充; ii）它可以由连接多边形的边组成; iii）它可以具有危险的边; iv）两个多边形可以在顶点处彼此接触;或者v）它可以具有断开的组件（诸如顶点、边和/或多边形）。因此，beta形状可以是非流形的。在三维情况下，参见[17]。5. BetaConcept计划BetaConcept程序是按照标准开发的，86J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）79~87(a)（b）第（1）款(c)（d）其他事项(e)（f）第（1）款图6.一组圆盘生成器、准三角形和对应于半径β的不同探测值的β复合体：（a）具有QT的输入圆盘，（b）对于微小的β1> 0的BC，（c）对于β2>β1的BC（无异常），（d）对于β3>β2的BC（异常），（e）β 4> β 3的BC，以及（f）β 5 = ∞的BC（BC与QT相同）。C++，MFC用于用户界面，OpenGL用于其图形，由六组函数组成 创建、选择、修改和删除盘式发电机 VD/VDs的计算、DT/QT的转换、BC的提取及其统计 偏移和混合 文件i/o 属性编辑 重放系统状态BetaConcept程序的图形用户界面，如图7所示，由三个部分组成：图形显示、统计显示（左下）和用户控制程序的菜单可通过屏幕5.1创建、选择、删除和转换磁盘生成器用户可以通过两种方式创建磁盘生成器：i）通过拖动按下的鼠标左键同时按下“center”键来一次创建一个磁盘生成器用户可以通过提供参数来确定网格的大小图8（a）显示了创建的两个磁盘生成器集群：一个是通过一次一个的方法创建的，另一个是通过3×5矩阵的网格模板创建的。有两种方法来选择磁盘：i）单击磁盘顶部的左按钮进行选择，ii）在按下“shift”键的同时，通过拖动按下鼠标左键来橡胶带方法可以选择J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）78~8687图7. BetaConcept程序图形用户界面。在矩形范围内的一组圆盘选定的磁盘可以通过简单地按下“删除”键删除所有生成的生成器都可以用鼠标平移，用菜单旋转，变换后的生成器可以返回到初始视图。放大和缩小也提供。（一）（b）第（1）款图8.在BetaConcept程序中为实体分配属性的不同方法：（a）生成器，Voronoi图和准三角形，（b）生成器，Voronoi图和beta复合体。5.2 属性编辑用户可以编辑所选实体的属性在盘的情况下，用户可以修改几何形状（即，坐标和半径）以及诸如盘的颜色、厚度、样式的呈现样式。一个磁盘也可以填充不同的颜色。其他实体，如Voronoi diagrams，准三角形，β复合体，β形状等。也可以以类似的方式进行修改在图8（a）中，使用不同的颜色来填充盘生成器，并且准三角测量也被不同地着色图8（b）显示了具有编辑属性的beta复合物5.3 计算VD、QT和BCBetaConcept程序在创建三个以上磁盘时计算VD并将其转换为QT。用户可以通过设置探头半径从QT中提取BCaβ值。可以通过调整滑动条或在菜单上键入值来设置β通过勾选/取消勾选菜单上的复选框，可以独立显示VD、QT和BC用户可以改变每个单形的可见性（即，顶点、边或面的可见性），并更改每个单形的样式。VD、QT和BC的统计信息显示在统计信息面板中。如果其中任何一个的状态发生变化，统计数据将自动改变。5.4 文件i/oBetaConcept程序有三种文件i/o模式磁盘生成器可以存储在ASCII文件中，稍后可以再次加载。图形面板中的当前可视化也可以存储在PDF文件中，以便在文档中使用本文中的所有图形都是使用此功能生成的。用户可以加载位图图像文件作为背景，如图9所示88J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）79~87图9.带有背景位图图像的BetaConcept程序。5.5 模拟（重播）BetaConcept程序按照当前显示的磁盘创建顺序或用户选择的顺序维护会话状态因此，通过按此顺序触发输入磁盘的创建顺序，用户可以通过逐个递增磁盘来捕获状态变化我们称这个过程为模拟。换句话说，用户可以通过点击菜单上的“模拟”按钮激活模拟功能来模拟VD、QT和BC的变化，该菜单有两个如果用户选择自动选项并以秒为单位设置时间间隔，则程序将通过按定义的时间间隔逐个递增磁盘如果用户选择手动，则用户可以通过单击控制面板上的下一步按钮来逐个增加磁盘5.6 偏移和混合BetaConcept程序可以计算偏移量δ> 0的修剪偏移。混合的计算也类似于偏移计算。程序首先计算β=δ的β形BS，然后提取边界节点BS存储在图形数据结构G=（VG，EG）中。一条奇异边eG∈EG意味着它的两个入射qt-胞腔是外部的，规则边缘意味着它的两个起始QT单元之一是外部的，另一个是内部的。一般来说，G是一个森林。设G={1，2，其中，n∈G是一个分量。对于G的每个分量，程序执行以下操作。如果所有的边都是规则的，它的图形结构直接用于连接偏移弧。否则，它会复制每个奇异边并创建一个循环正确的方向结构注意，每个边的方向提供了如何选择两个原子边界之间的两个交点之间的相交点的信息给定β形BS，偏移-该算法简单明了，在最坏情况下的计算复杂度为O（m），其中m表示图上的边数。最坏情况下，时间复杂度为O（n）。这一观点继承了[19]中的早期观点图10示出了四个不同探头的偏移和与Voronoi图VD和β形BS的混合在每幅图中，黑色磁盘是输入磁盘，阴影磁盘是偏移磁盘。注意，偏移的边界被正确地计算，并且连续弧之间的交点被精确地定位在Voronoi图VD上。红色链是探针定义的混合圆盘的边界偏移和混合都是使用阴影区域内显示的beta形状计算的6. 结论本文给出了平面上Voronoi图与拟三角剖分图之间的对偶映射的定义特别地，我们首次引入了拟单纯复形的概念，并证明了拟三角剖分是拟单纯复形。我们还介绍了BetaConcept程序，该程序是二维Voronoi图，准三角剖分及其beta复形的实现BetaConcept程序可以帮助用户了解Voronoi图、准三角剖分和平面中的β复合体的强大概念和能力，并希望将理解扩展到其三维对应物。通过使用该程序，用户还可以识别这些结构在平面上的应用我们欢迎对这些结构、BetaConcept和BetaMol的任何建议和合作。致谢这项工作得到了国家研究基金会的支持J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）78~8689（一）（b）第（1）款（c）第（1）款（d）其他事项图10.对于给定的输入盘，偏移和与VD和BC混合：（a）对于β1> 0的微小探针，（b）对于小探针（β2>β1），（c）对于中等探针（β3> β2），以及（d）对于大探针（β4> β3）。由 韩 国 政 府 （ MSIP ） 资 助 的 韩 国 （ NRF ） 赠 款2012R1A2A1A05026395）。引用[1] Okabe A，Boots B，Sugihara K，Chiu SN.空间镶嵌：90J. Kim等人/Journal of Computational Design and Engineering，Vol.号12（2014）79~87Voronoi图的概念和应用。Chichester：John Wiley Sons;2000.696页[2]Cho Y，Kim JK，Ryu J，Won CI，Kim CM，Kim D，Kim DS. BetaMol：一个基于β-复合物和准三角测量的分子建模、分析和可视化软件。高级机械设计、系统与制造杂志。2012; 6（3）：389-403.[3]Cho Y，Kim D，Kim DS.三维球体Voronoi图的拓扑表示。国际CAD/CAM杂志。2005; 5（1）：59-68.[4]放大图片作者：Kim D.三维球的欧几里德Voronoi图及其边跟踪计算。计算机辅助设计。2005; 37（13）：1412-1424.[5]Kim D，Kim DS.三维球体Voronoi图的区域展开计算机辅助设计。2006; 38（5）：417-430.[6]李 凯 CAD/CAM/CAE 系 统 原 理 。 Upper Saddle River（NJ）：Prentice Hall; 1999.640磅[7]作者：Lee D.平面Voronoi图的推广SIAM Journal onComputing.1981; 10（1）：73-87.[8]沙里尔·M一类平面圆盘的交线与最近对问题。SIAMJournal on Computing. 1985; 14（2）：448- 468.[9]Yap CK。一组简单曲线段的Voronoi图的一个O（n logn）算法离散计算几何学1987; 2：365-393.[10] Gavrilova M，Rokne J.圆和线段的动态vd的交换条件。计算机辅助几何设计1999; 16（2）：89-106.[11] 杉原湾普通Voronoi图对广义Voronoi图的逼近图形模型和图像处理。1993; 55（6）：522-531.[12] 放大图片作者：Kim DS，Kim D，Sugihara K.圆集的Voronoi图由点集的Voronoi图得到：I. topology.计算机辅助几何设计2001; 18：541-562.[13] 放大图片作者：Kim DS，Kim D，Sugihara K.圆集的Voronoi图来自点集的Voronoi图：II。几何计算机辅助几何设计2001; 18：563-585.[14] Kim DS，Kim D，Cho Y，Sugihara K.三维空间中的准三角剖分与界间数据结构计算机辅助设计。2006; 38（7）：808-819.[15] Kim DS，Cho Y，Sugihara K.拟三角剖分上的拟世界与拟算子。计算机辅助设计。2010; 42（10）：874-888.[16] Kim DS，Cho Y，Ryu J，Kim JK，Kim D.分子中球形原子的准三角剖分和β-复合物中的反常现象计算机辅助设计。2013; 45（1）：35-52.[17] [10] Kim DS，Cho Y，Sugihara K，Ryu J，Kim D.三维β-形状和β-复合物通过准三角测量。计算机辅助设计。2010; 42（10）：911-929.[18] Kim DS，Kim JK，Cho Y，Kim CM.在拟三角剖分中查询单形。计算机辅助设计。2012; 44（2）：85- 98.[19]Kim DS.使用Voronoi图和两个一堆堆。计算机辅助设计。1998; 30（14）：1069-1076.