关于高阶Voronoi图快速生成算法的研究

论文摘要

高阶Voronoi图是普通Voronoi图的一种重要推广,在解决平面点集多个点的邻近问题中有着广泛的应用。然而,以往的高阶Voronoi图生成算法构造代价较高,时间复杂度较大,因而限制了高阶Voronoi图在实际应用中的推广。本文介绍了k （1≤k <n）阶最近点Voronoi图,k阶最远点Voronoi图和k阶有顺序Voronoi图的定义及性质,对k阶Voronoi图,k阶有顺序Voronoi图在生成算法方面进行了深入研究,并在分析已有高阶Voronoi图生成算法的基础上,依据“限定上界（Fixed Upper Bound）”定理,提出了一种基于屏幕自适应分区实现局部查找k个邻近点的快速生成k阶Voronoi图以及k阶有顺序Voronoi图的算法。除此之外,该算法还能用于生成多种不同形式的高阶Voronoi图。这种生成k阶Voronoi图的算法思路清晰,数据结构简洁,在保证图形效果的前提下,生成速度得到了显著提高。该算法已在Visual C++环境下实现,从而验证了算法的有效性。

论文目录

• 摘要
• Abstract
• 绪论
• 第1章 Voronoi 图的简介
• 1.1 Voronoi 图产生的历史
• 1.2 Voronoi 图的定义
• 1.3 Voronoi 图的性质
• 1.4 Voronoi 图的主要生成算法
• 第2章 高阶Voronoi 图
• 2.1 概述
• 2.2 k 阶Voronoi 图
• 2.2.1 k 阶最近点 Voronoi 图
• 2.2.2 k 阶最远点 Voronoi 图
• 2.3 k 阶有顺序Voronoi 图
• 2.3.1 k 阶有顺序 Voronoi 图的定义
• 2.3.2 k 阶有顺序 Voronoi 图的性质
• 第3章 高阶Voronoi 图生成算法
• 3.1 传统的高阶 Voronoi 图生成算法概述
• 3.2 预备知识
• 3.3 生成k 阶 Voronoi 图的算法
• 3.4 k 阶有顺序Voronoi 图生成算法
• 3.5 算法中的关键技术
• 第4章 算法效率分析
• 结论
• 参考文献
• 附录
• 致谢