|
|||||
|
|
| 使用动态矩形窗求最近点对的几何算法 | |
| 引用本文： | 姜春茂,张国印.使用动态矩形窗求最近点对的几何算法[J].哈尔滨工程大学学报,2013(3):350-357. |
| 作者姓名： | 姜春茂 张国印 |
| 作者单位： | 哈尔滨工程大学计算机科学与技术学院;哈尔滨师范大学计算机科学与信息工程学院 |
| 基金项目： | 国家自然科学基金资助项目(61073042);黑龙江省自然科学基金资助项目(F201139) |
| 摘 要： | 针对几种经典算法的效率问题,提出了一种最近点对求解算法:算法预先找到X、Y坐标轴最大、最小坐标值,将点集按某坐标轴排序,并根据鸽巢原理计算最近点对i间距离的上限,由此上限将整个点集分割成不同的区域,最后在每个区域中通过动态缩小每个点的矩形窗减少了算法的计算次数.通过理论证明和实际验证得出:初始点集有序时算法的时间复杂度为O(n);无序时在一般情况下为O(n),最坏情况下为O(nlogn);算法的时间复杂度和运行时间明显优于经典分治算法和基于底函数的算法. |
| 关 键 词： | 动态矩形窗 最近点对 几何算法 鸽巢原理 |
| 本文献已被 CNKI 等数据库收录！ | |