题目
最接近点对问题求解中应用到了鸽舍原理。HA. 正确B. 错误
最接近点对问题求解中应用到了鸽舍原理。H
A. 正确
B. 错误
题目解答
答案
A. 正确
解析
最接近点对问题是计算几何中的经典问题,通常采用分治算法求解。其核心思路是将点集按x坐标划分左右两部分递归处理,最后合并时需检查跨越左右的点对。鸽舍原理(抽屉原理)在此处用于优化合并步骤:当垂直带内点数超过一定数量时,必然存在距离小于当前最小值的点对,从而减少比较次数。因此,题目中的说法正确。
关键概念解析
- 最接近点对问题:在平面上找出距离最近的两个点,常用分治法实现,时间复杂度为$O(n \log n)$。
- 鸽舍原理:若将多于$k$个物品放入$k$个容器,则至少有一个容器包含至少两个物品。在算法中用于证明垂直带内点数过多时必然存在近邻。
算法步骤中的应用
- 分治划分:将点集按x坐标分为左右两部分,递归求解左右子问题,得到当前最小距离$d$。
- 构造垂直带:以左右边界中点为基准,构造宽度为$2d$的垂直带,筛选带内所有点。
- 按y坐标排序:将带内点按y坐标排序,逐个检查每个点后方的最多5个点,若发现更近距离则更新$d$。
- 鸽舍原理的作用:若带内点数超过$6$个,则根据鸽舍原理,至少存在两个点在同一垂直单元内,距离必然小于$d$,此时可提前终止检查。