高阶Voronoi图的结晶生成

详细信息    查看全文 | 推荐本文 |

英文篇名：Crystal Growth of Higher-order Diagrams 作者：周恩辉 ; 刘淑娟 英文作者：ZHOU Enhui;LIU Shujuan;College of Mathematics and Information Sciences,Hebei Normal University; 关键词：Voronoi图 ; 高阶Voronoi图 ; 结晶生长 英文关键词：Voronoi diagrams;;higher-order diagrams;;ctystal growth 中文刊名：HBSZ 英文刊名：Journal of Hebei Normal University(Natural Science Edition) 机构：河北师范大学数学与信息科学学院; 出版日期：2014-03-19 23:13 出版单位：河北师范大学学报(自然科学版) 年：2014 期：v.38;No.154 基金：河北省高等学校科学技术研究项目(QN20131159) 语种：中文; 页：HBSZ201402009 页数：5 CN：02 ISSN：13-1061/N 分类号：32-36

摘要

Voronoi图是计算几何的重要分支.高阶Voronoi图是Voronoi图在阶数方面的扩展,在许多领域有着重要应用.本文提出了生成高阶Voronoi图的结晶生长方法.该方法以生成元为初始生长点,使用4-连通模板、8-连通模板或二者交替使用进行结晶生长,最后对不同颜色的区域分别进行处理,就会得到基于城区距离、棋盘距离或欧氏距离的各种高阶Voronoi图.
        Voronoi diagrams is one of main branches in computational geometry.Higher-older voronoi diagrams is a kind of spread of voronoi in orders and which is used in many fields.In this paper,crystal growth is presented to construct higher-older Voronoi diagrams.In the method,generators of Voronoi diagrams are regarded as initial growing points,then the crystallization process begins from these generators with 4-point template,8-point template or alternating usage about 4-point template and 8-point template. By separating different colour regions,we can obtain higher-order voronoi diagrams based on the city zone distance,the chessboard distance and the euclid distance.

引文

[1]SHAMOS M I,HOEY D.Closest-point Problems[C]//Proceedings of the Sixteenth Annual Institute of Electrical and Electronic Engineers Symposium on the Foundations of Computer Science,Washington:IEEE Computer Society,1975:151-162.
    [2]周培德.计算几何[M].北京:清华大学出版社,2000.
    [3]LEE D T.On k-nearest Neighbor Voronoi Diagrams in the Plane[J].IEEE Transactions on Computers,1982,31(6):478-487.
    [4]FRANCO P.PREPARATA,MICHAEL I.庄心谷译.计算几何导论[M].北京:科学出版社,1990.
    [5]CHAZELLE B,EDELSBRUNNER H.An Improved Algorithm for Constructing Kth-order Voronoi Diagrams[J].IEEE Transactions on Computers,1987,36(11):1349-1354.
    [6]CLARKSON K L.New Applications of Random Sampling in Computational Geometry[J].Discrete and Computational Geometry,1987,2(1):195-222.
    [7]BOISSONNAT J D,DEVILLERS O,TEILLAUD M.A Semidynamic Construction of Higher-order Voronoi Diagrams and Its Randomized Analysis[J].Algorithmic,1993,9(4):329-356.
    [8]BOISSONNAT J D,TEILLAUD M.A Hierarchical Representation of Objects:the Delaunay Tree[C]//Proceeding of the Second ACM Symposium on Computational Geometry,New York:ACM Press,1986:260-268.
    [9]BOISSONNAT J D,TEILLAUD M.On the Randomized Construction of the Delaunay Tree[J].Theoretical Computer Science,1993,112(2):339-354.
    [10]田孝康村岛定行.2次元離散画面上の高次のボロノイ作成について[M].电子情报通信学会论文志.1999:283-288.
    [11]顾晓青.高阶Voronoi图的生成及应用[D].石家庄:河北师范大学,2003.
    [12]曹清洁.障碍Voronoi图的结晶生成[D].石家庄:河北师范大学,2004.