基于分治法的三维最近点对问题的研究

• 作者: 林泽瀚
• 来源期刊: 电子元器件与信息技术
• 关键词: 三维最近点对 计算几何 分治法 双指针 鸽巢原理
• 年，卷（期）: 2021,（5）
• 所属期刊栏目: 大数据与信息处理
• 页码范围: 44-47
• 页数: 4页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19772/j.cnki.2096-4455.2021.5.020

摘要

最近点对问题被广泛应用于工程项目之中,近年来,由于大数据计算和人工智能等领域的兴起,许多计算领域对三维最近点对问题的运用更加广泛.分治法求解最近点对是计算几何领域的经典算法.本文通过对传统的二维最近点对问题进行分析并推广到三维空间下,利用分治法的思想和鸽巢原理,设计出两种高效求解三维最近点对的方法,对比朴素做法,在时间复杂度上有显著的优化.