D. BO Algorithm: Strategy
数学大学
D. BO Algorithm: Strateg
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
D. BO Algorithm: Strateg
计算几何 · 02. Geometric Intersection
Proximity & Separability
桶算法的两个关键性质：邻近性（近点同桶或邻桶）与分离性（最大间隔必跨桶）。
邻近性
相近的点落入相同或相邻的桶
分离性
鸽巢原理保证最大间隔出现在桶之间
Comparability & Ordering
桶内元素的可比较性：桶内不必排序，只需知道桶的边界即可跨桶比较。
免排序
只记每桶的最小值与最大值
跨桶比较
相邻非空桶的边界差即为候选间隔
Data Structures
桶算法的数据结构：桶数组，每桶只存最小值与最大值两个数。
桶数组
定长数组按下标直接寻址
两数字段
bMin 与 bMax，O(1) 更新
Possible Cases
情况枚举：点数与桶数的相对关系、空桶分布决定算法行为。
点少桶多
大量空桶，候选间隔只在相邻非空桶间产生
点密桶少
桶内多点，桶间界仍界定间隔下界
本节要点
- ✓邻近性与分离性是正确性根基
- ✓桶内免排序，只记 min/max
- ✓空桶分布决定候选间隔的来源
延伸主题：实现桶结构的 min/max 记录构造极端分布测试算法
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1桶算法为什么「只存桶内 min 与 max」就够？
参考答案桶内相邻差一定小于该桶跨度，而跨桶间隔只与前一桶的 max 和后一桶的 min 有关。桶内的内部细节对候选间隔毫无贡献——信息裁剪精确到最小必需。
2桶法中「邻近性」成立的前提是桶宽如何选取？
参考答案桶宽取总跨度除以约 n−1（与期望相邻差同量级）时，邻近性最强：近点几乎必同桶或邻桶。桶宽是邻近性与空桶开销的调节旋钮，不是固定值。
3若所有点挤在一个桶里会发生什么？说明什么前提被破坏？
参考答案说明「均匀分布」假设严重不成立：数据聚集使桶失去区分能力，桶内仍需排序才能算间隔。退化数据下应改用扫描线法或先做粗分再递归细分。