使用动态矩形窗求最近点对的几何算法

• 作者: 姜春茂 张国印
• 来源期刊: 哈尔滨工程大学学报
• 学科: 工学
• 关键词: 动态矩形窗 最近点对 几何算法 鸽巢原理
• 年，卷（期）: 2013,（3）
• 页码范围: 350-357
• 页数: 8页
• 分类号: TP301.6
• 字数: 6415字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-7043.201204044

摘要

针对几种经典算法的效率问题,提出了一种最近点对求解算法:算法预先找到X、y坐标轴最大、最小坐标值,将点集按某坐标轴排序,并根据鸽巢原理计算最近点对i间距离的上限,由此上限将整个点集分割成不同的区域,最后在每个区域中通过动态缩小每个点的矩形窗减少了算法的计算次数.通过理论证明和实际验证得出:初始点集有序时算法的时间复杂度为O(n)；无序时在一般情况下为O(n),最坏情况下为O(nlogn)；算法的时间复杂度和运行时间明显优于经典分治算法和基于底函数的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张国印	哈尔滨工程大学计算机科学与技术学院	162	1407	18.0	28.0
2	姜春茂	哈尔滨工程大学计算机科学与技术学院	6	33	3.0	5.0