Voronoi图的构建与受限区域内的最近邻查询方法研究

摘要：

Voronoi图在空间数据查询、数据挖掘、图像处理、模式识别和智能交通管理等方面具有重要的作用.为了简化构建的复杂性和提高构建效率,基于分治法、启发式局部优化策略和局部数据点的扫描线动态更新策略,提出了基于凸包的Voronoi图生成方法,给出了Create_ Voronoi()算法.进一步,为了弥补已有近邻查询方法无法处理受限区域内的最近邻查询的不足,基于Voronoi图研究了受限区域内的同质和异质最近邻查询方法,分别提出了TVor_NN()算法和YVor_ NN()算法.理论研究和实验分析表明,提出的研究方法在Voronoi图的构建和受限范围的最近邻查询等方面具有较大的优势.

关键词：Voronoi图、Delaunay三角形、最近邻查询、受限区域

所属期刊栏目：41

分类号：TP311(计算技术、计算机技术)

资助基金：黑龙江省教育厅科学技术研究项目12541122

在线出版日期：2014-11-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：220-224,247