%0 Journal Article
%T Design and Implementation of an Approximately Linear Average-Case Complexity Algorithm for Voronoi Diagram of Planar Point Set<br>近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现
%A 廖士中
%A 王晓东
%J 计算机科学
%D 2002
%I 
%X 1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提
%K 计算几何
%K Voronoi图
%K 增量算法
%K 平面点集
%K 近似线性平均复杂性
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=9964CFBDC996DB94&yid=C3ACC247184A22C1&vid=771469D9D58C34FF&iid=9CF7A0430CBB2DFD&sid=B9704B40A4225A24&eid=80A07035DF96B0C4&journal_id=1002-137X&journal_name=计算机科学&referenced_num=1&reference_num=3