CLRS 33.4 最近点对算法题解详解：分治正确性、检查点数下界与 L_m 度量推广

文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于开源仓库 CLRS Solutions算法导论第三版题解集合中 docs/Chap33/33.4.md 的练习题解答系统剖析第 33.4 节寻找最近点对Finding the closest pair of points的六道进阶习题包括对合并阶段检查点数 7→5 的充分性论证、分治划分线选取的退化场景、以及将算法推广到 $L_1$曼哈顿距离与 $L_\infty$切比雪夫距离等非欧氏度量。读完本文你将掌握最近点对分治算法在每个细节边界共线点、严格不等式、度量更换、预排序消除上的处理技巧并能直接迁移到实际几何算法工程实现中。1. 算法背景练习所围绕的最近点对分治框架33.4 节的六道练习题全部围绕课本正文介绍的分治版最近点对算法展开题解中反复出现的核心要素如下理解它们才能读懂后续每道题的讨论预排序数组 $X$ 与 $Y$算法开始时分别按 $x$ 坐标和 $y$ 坐标对全部 $n$ 个点排序为递归与合并阶段做准备递归划分 $P_L$ 与 $P_R$通过一条垂直于 $x$ 轴的分割线 $l$把点集大致平分各约 $n/2$为左右两个子集分别递归求解$\delta$ 的定义设 $\delta \min(\delta_L, \delta_R)$ 为左右两侧递归结果中的较小最近距离最终答案要么来自某一侧内部要么来自跨越分割线 $l$ 的一对点$\delta \times 2\delta$ 矩形跨线候选点只可能出现在以 $l$ 为中线的、宽 $2\delta$ 高 $2\delta$ 的窄带内题解与正文正是通过统计该矩形内可容纳的点数来限定需要检查的候选数量$Y$ 数组与后继点检查把窄带内的点按 $y$ 坐标排成数组 $Y$对每个点只需检查 $Y$ 中紧随其后的若干个点即可找到跨线最近对图 33.11(b)正文中展示 $\delta \times 2\delta$ 矩形内点分布示意图题解 33.4-2 专门讨论了该图所示非严格不等式情形与真实最短距离情形的差异。在仓库的站点导航 mkdocs.yml 中本页注册于 VII Selected Topics → 33 Computational Geometry 分组下与 docs/Chap33/33.3.md凸包、docs/Chap33/33.1.md线段性质、docs/Chap33/33.2.md线段相交判定共同构成完整的计算几何章节便于对照学习。2. 练习 33.4-1Professor Williams 的只检查 5 个点方案为何有缺陷原题Professor Williams 提出了一种让最近点对算法对数组 $Y$ 中每个点只检查其后 5 个点的方案其想法是总是把位于分割线 $l$ 上的点划入集合 $P_L$。这样一来直线上不可能出现一个点在 $P_L$、一个点在 $P_R$ 的重合点对于是 $\delta \times 2\delta$ 矩形内至多能容纳 6 个点而非正文给出的 7 个从而只需检查 5 个后继位置即可。问该方案存在什么缺陷解答要点关键在于选择分割线 $l$ 时我们可能无法实现对点集的均分even split。也就是说左右两侧的点数未必各自约等于 $n/2$。例如假设所有点恰好排列在一条竖直线上那么当我们对左侧子集递归时问题规模完全没有被缩小更谈不上按因子 2 缩小而在这种配置下处理右侧子集时还可能遇到子集大小小于 2 的情况无法构成一对点。深入分析这道题点破了分治最近点对算法对平衡划分的隐式依赖。课本正文能推出 $T(n) 2T(n/2) O(n) O(n\lg n)$前提是每次划分大致对半。Professor Williams 的方案试图通过所有共线点归入一侧来压低矩形内的点数从 7 压到 6从而把后继检查从 7 个降到 5 个代价却是牺牲了划分的平衡性——这正是典型的用正确性/复杂度换常数优化陷阱。当所有点共垂直线时若按 $x$ 坐标排序中点位置的点与其余点 $x$ 坐标相同任意选择竖直线 $l$ 都无法把点集分开若强行把共线点全部归入 $P_L$递归树退化为链状左子问题规模仍是 $n$右子问题可能为空或不足 2 个点算法退化且无法正常返回最近对。本题的教训是任何试图优化合并阶段检查点数的技巧都必须先保证递归划分的平衡性不受破坏否则 $O(n\lg n)$ 的复杂度前提将崩塌。3. 练习 33.4-2证明只需检查 $Y$ 中每个点之后的 5 个位置就足够原题证明对数组 $Y$ 中每个点实际上只需检查其后的 5 个数组位置即可即矩形内点数上限可以从 7 收紧到 6。解答要点因为我们只关心最短距离所以跨线一对点的真实距离 $\delta$ 必须严格小于$\delta$否则这一对不会成为全局最近对。正文中的图 33.11(b) 只画出了非严格不等式即 $x$ 坐标恰与 $l$ 相差 $\delta$ 的点也被算入的情形。若排除 $x$ 坐标与 $l$ 恰好相差 $\delta$ 的点那么 $\delta \times 2\delta$ 矩形内至多只能放置 6 个点于是对 $Y$ 中每个点检查其后 5 个位置就足够了。深入分析这里的关键是严格小于四个字如何把上界从 7 收紧到 6在非严格版本中矩形左、右边界上即 $x$ 坐标与 $l$ 恰差 $\delta$可以各排 3 个点再加上中线上可能的点构成 7 个点的极端配置这是正文选择检查 7 个后继的原因但真正的候选对距离必须 $ \delta$。若某点的 $x$ 坐标与 $l$ 恰差 $\delta$它与 $l$ 另一侧任何点的距离都至少为 $\delta$由 $L_2$ 度量下水平分量决定不可能成为跨线最近对因此这类点可以直接从计数中剔除剔除后矩形内最多只剩 6 个点每个 $y$ 层次上至多左右各 1 个故检查 5 个后继位置即可覆盖全部潜在对手。这一紧化论证在工程上有实际意义它把合并阶段的常数从 7 降到 6检查 5 个位置在 $n$ 极大时对常数因子的改善是真实可感的且正确性不受影响。4. 练习 33.4-3把算法推广到 $L_1$曼哈顿距离原题平面上两点 $p_1$、$p_2$ 的 $L_m$-距离定义为 $(|x_1 - x_2|^m |y_1 - y_2|^m)^{1/m}$欧氏距离即 $L_2$-距离。请修改最近点对算法以使用 $L_1$-距离又称曼哈顿距离。解答要点对算法的分析中绝大部分推导仅依赖三角形不等式即可成立因此依然有效。唯一的主要差异在于考察 $\delta \times 2\delta$ 矩形内能容纳多少点与正文图中展示的 8 个点相比在 $L_1$ 度量下我们还可以把点放到矩形划分成的两个正方形的中心从而多塞进 2 个点。这意味着需要检查 $Y$ 中距离当前点至多 9 个位置的点而非 $L_2$ 下的 7 个位置。这一改动不影响算法的渐近复杂度且是 $L_2 \to L_1$ 切换时唯一需要修正的地方。深入分析为什么 $L_1$ 会允许矩形内塞下更多点因为矩形内点对能否互相成为候选取决于其 $L_1$ 距离是否 $ \delta$而 $L_1$ 度量在棋盘式路径下对某些几何排列比 $L_2$ 更宽松在 $L_2$ 下$\delta \times 2\delta$ 矩形被中线分成两个 $\delta \times \delta$ 正方形每个正方形内 $L_2$ 直径恰好为 $\sqrt{2},\delta \delta$故不能简单在每个正方形中心放点在 $L_1$ 下$\delta \times \delta$ 正方形的对角线长度按 $L_1$ 度量恰为 $2\delta$而中心到任意顶点四角的 $L_1$ 距离为 $\delta$等于而非超过阈值——结合距离必须严格 $\delta$的论证中心点仍可被纳入候选配置因此矩形内容量从 8 增至 10即需要检查 9 个后继位置。对实现者而言本题的落地点很明确切换距离度量时只需替换距离函数并同步调整合并阶段的检查范围7 → 9递归结构、预排序流程与渐近复杂度全部保持不变。曼哈顿距离在网格化地图、路径规划、芯片布线等场景中比欧氏距离更贴近真实代价因此这一推广具有直接的工程价值。5. 练习 33.4-4把算法推广到 $L_\infty$ 距离原题平面上两点 $p_1$、$p_2$ 的 $L_\infty$-距离为 $\max(|x_1 - x_2|, |y_1 - y_2|)$请修改最近点对算法以使用 $L_\infty$-距离。解答要点只需按章节中描述的分治算法原样运行把 $|P| \le 3$ 时的暴力搜索以及 $Y$ 中对每个点检查其后 7 个点的过程改为使用 $L_\infty$ 距离计算。由于 $L_\infty$ 距离总是小于等于欧氏距离实际比较中可理解为不小于关系下的一个便捷上界$\delta \times 2\delta$ 矩形内至多有 8 个点需要检查因此修改后的算法仍然正确且运行时间与原来相同。深入分析$L_\infty$ 度量把距离简化为两个坐标差中的较大者几何直觉上相当于把平面划分成轴对齐的正方形棋盘。这带来两个便利候选点上限分析更简单在 $L_\infty$ 下$\delta \times 2\delta$ 矩形被中线分割成的两个 $\delta \times \delta$ 正方形其直径按 $L_\infty$恰为 $\delta$矩形内点与点之间满足 $L_\infty \delta$ 的组合不会超出 8 个的计数因此检查范围保持 $O(1)$ 常数实现改动最小与 33.4-3 不同这里甚至不需要扩大检查范围只需要替换距离函数即可暴力基线$|P| \le 3$与合并阶段扫描逻辑均可原样复用。结合 33.4-3 与 33.4-4 可以提炼出一个通用结论最近点对分治算法对度量只敏感于$\delta \times 2\delta$ 矩形内容量这一处只要新度量满足三角形不等式其余证明递归正确性、$O(n\lg n)$ 递推都自动成立。这一观察也解释了为什么 33.4-3 的解答特意强调唯一需要修正的地方。6. 练习 33.4-5大量点共垂直线时的划分与归属判定原题假设传给最近点对算法的点中有 $\Omega(n)$ 个点是共垂直的covertical即 $x$ 坐标相同。请说明如何确定集合 $P_L$ 与 $P_R$以及如何判定 $Y$ 中每个点属于 $P_L$ 还是 $P_R$使算法运行时间仍保持 $O(n\lg n)$。解答要点选择一条大致平分点数的竖直线 $l$然后对位于线上的点任意挑选一个子集划归 $P_L$、其余划归 $P_R$ 即可不会产生问题。由于算法分析本来就允许 $P_L$ 与 $P_R$ 中都有元素位于 $l$ 上这样处理依然保证正确性。为了让归属判定更容易可以把需要进入 $P_L$ 的最低的若干点挑出其余较高的点划入 $P_R$这样只需知道当前在 $Y$ 中的索引即可判断该点属于 $P_L$ 还是 $P_R$。深入分析本题是 33.4-1 的正向解法——上一题指出共线点全归一侧会破坏平衡本题给出正确的平衡化策略平衡优先先按 $y$ 坐标或 $x$ 坐标排序后的下标找到大致中位数位置把共线点按需拆分保证 $P_L$、$P_R$ 规模各约 $n/2$从而保住 $T(n) 2T(n/2) O(n)$ 的递推式正确性不受影响正文合并阶段的论证允许跨线候选对中两点分别来自 $P_L$ 与 $P_R$即便它们 $x$ 坐标相同恰好都在 $l$ 上只要其 $y$ 差满足检查条件仍会被 $Y$ 的相邻扫描捕获O(1) 归属判定把共线点按 $y$ 排序后前 $k$ 个低的进 $P_L$、其余进 $P_R$属于哪一侧就退化为一次下标比较扫描 $Y$ 时无需查找保持合并阶段线性时间。这三点合起来保证了即使在最坏分布大量点共享同一 $x$ 坐标下算法依然以 $O(n\lg n)$ 运行。7. 练习 33.4-6消除 $Y$ 数组的预排序用合并保持 $O(n\lg n)$原题建议对最近点对算法做一处改动使得不必预先对 $Y$ 数组排序但运行时间仍为 $O(n\lg n)$。提示合并递归返回的有序数组 $Y_L$ 与 $Y_R$ 以形成有序数组 $Y$。解答要点在返回最近距离的同时让算法额外返回传入点集按 $y$ 坐标排序后的数组 $Y$。具体做法是将两次递归调用各自返回的 $Y_L$ 与 $Y_R$ 做归并得到当前层的 $Y$。到达基准情形$n \le 3$时直接用插入排序把元素按 $y$ 坐标排好。由于每次归并耗时线性不会改变运行时间的递归方程因此整体仍是 $O(n\lg n)$。深入分析这个优化消除了算法中一个全局预排序的冗余其背后的复杂度账目值得仔细核算原算法在入口处对 $Y$ 做一次排序代价 $O(n\lg n)$随后每次递归调用都要从全量 $Y$ 中筛选出属于当前子集的点——筛选本身是线性的但配合递归后每层都要重新遍历若实现不当会引入额外 $O(n\lg n)$ 甚至更糟的开销改进后每一层递归只做有序子数组归并设该层规模为 $m$归并代价 $O(m)$于是递推式变为 $T(n) 2T(n/2) O(n)$解得 $T(n) O(n\lg n)$与预排序方案一致但省去了全局排序 逐层筛选的常数开销与实现复杂度基准情形用插入排序处理 $n \le 3$ 的小数组代价为常数不会破坏递推式——这也与分治算法小规模退化到简单排序的通用模式一致可参考仓库中 docs/Chap02/2.1.md 对插入排序的分析。本题展示的递归顺便返回辅助有序结构手法与归并排序见 docs/Chap02/2.3.md的合并思想一脉相承是分治算法中复用子问题结构的经典范式。8. 仓库阅读路径与延伸学习本章主文档docs/Chap33/33.4.md 即本文所解析的六道练习题原始题解站点导航入口见 mkdocs.yml 中 33.4 Finding the closest pair of points 条目同章前置内容docs/Chap33/33.1.md线段性质与叉积、docs/Chap33/33.2.md线段相交判定、docs/Chap33/33.3.md凸包与 GRAHAM-SCAN构成计算几何的完整知识链本章综合题docs/Chap33/Problems/33-1.md凸层 convex layers等 Problem 文件提供了把凸包与点集几何结合的更高阶练习站点技术栈本仓库使用 MkDocs Material for MkDocs 构建见 docs/index.md 与 mkdocs.yml数学公式由 KaTeX 渲染docs/js/katex.js阅读源码时可直接在浏览器中打开对应 Markdown 页查看排版效果。总结33.4 的六道习题从四个维度把最近点对分治算法锤炼到位——划分平衡性33.4-1、33.4-5、检查点数紧化33.4-2、度量泛化33.4-3、33.4-4与预排序消除33.4-6。掌握了这些边界条件你就能在真实工程中自信地实现、改造并证明这一经典 $O(n\lg n)$ 几何算法。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐QtScrcpy 完整指南免费安卓投屏、键鼠控制与多机群控一次讲清QtScrcpy 完整指南免费安卓投屏、键鼠控制与多机群控一次讲清 QtScrcpy 是一款免费开源的安卓投屏与远程控制工具基于 scrcpy 重构用 U桌面应用音视频我的电视 my-tv智能电视与安卓盒子看直播的 10 分钟上手指南3 种安装方式 4 个日常操作我的电视 my tv智能电视与安卓盒子看直播的 10 分钟上手指南3 种安装方式 4 个日常操作 我的电视my tv是一款免费开源的 Androi音视频直播如何高效实现最近点对问题分治算法的终极指南如何高效实现最近点对问题分治算法的终极指南 最近点对问题是计算机科学中经典的几何问题其核心是在平面上找到距离最近的一对点。分治算法作为解决此类问题的高效方法文档教程知识库上一篇BetterJoy终极指南 - 如何免费将Switch控制器变为PC游戏神器下一篇BetterJoy完整指南5分钟让Switch手柄在电脑上完美工作创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考