数学大学
A. Preliminary
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
A. Preliminary
计算几何 · 02. Geometric Intersection
EU
一维间隔问题的基本设定：给定实轴上的 n 个点，研究相邻点的间隔。
输入
实轴上无序的 n 个实数点
核心量
排序后相邻两点的差值序列
Min-Gap
最小间隔：排序后相邻点差的最小值，最近点对在一维的形态。
定义
相邻差的最小值即 Min-Gap
平凡解
排序后一趟线性扫描即得
Max-Gap
最大间隔：排序后相邻差的最大值，鸽巢原理可给出线性时间算法。
定义
相邻差的最大值即 Max-Gap
线性算法
按桶均匀分划，最大间隔必跨桶，桶内不必比较
IEU
间隔问题的输出与推广：从一维到高维最近点对的桥梁。
推广
一维 Min-Gap 是高维最近点对问题的退化形态
高维困难
二维以上需要分治与条带合并技巧
本节要点
- ✓一维间隔问题：排序后看相邻差
- ✓Min-Gap 线性扫描可得
- ✓Max-Gap 用鸽巢桶法线性时间
延伸主题：实现线性时间 Max-Gap思考高维最近点对怎么分治
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1Max-Gap 的线性算法为什么敢跳过桶内比较？
参考答案鸽巢原理：n 个点放入 n−1 个等宽桶，若最大间隔在桶内，则该桶占据的区间超过总跨度均分值，与其他桶的占位矛盾。因此最大间隔必然出现在「跨桶」的位置，桶内比较全无必要。
2Min-Gap 有没有可能不排序就线性求解？
参考答案一维 Min-Gap 本质依赖相邻关系，跳过排序就需要哈希分桶或间接结构，通常仍以排序的 O(n log n) 为最实用路径；Max-Gap 则靠鸽巢桶法实现真线性。两者难度不对称。
3桶宽选得过大或过小分别会怎样？
参考答案桶太宽：最大间隔可能落在桶内，跳过桶内比较就不再成立，算法失效。桶太窄：桶数暴增、内存与空桶遍历开销上升。以总跨度除以 (n−1) 为基准微调是常见做法。