B题参考文献 几何不确定区域的直径算法

2744557306

Computational Geometry: An Introduction（1985）是计算几何领域的奠基性教科书，由 Franco Preparata 和 Michael Shamos 合著。Shamos 在1978年的耶鲁大学博士论文中开创了"计算几何"这个学科方向，这本书则是把他的工作系统化整理成教材。你提到的第4章和第5章分别讲了两类核心问题：

---

第4章：凸包（Convex Hulls）

凸包是计算几何最基本的结构——给定平面上一堆点，凸包就是能包住所有点的最小凸多边形，就像在点集外面套一根橡皮筋。这一章讲了：

为什么要算凸包？ 因为很多几何问题在凸包上做比在原始点集上做简单得多。比如求最远点对、求点集直径，如果直接两两比较需要 O(n²)，但在凸包上做只需要 O(n)。凸包是很多算法的"预处理步骤"——先把问题简化到凸多边形上。

凸包算法。 书中介绍了经典的 Graham 扫描法（按极角排序后逐点入栈、检查转向）和分治法（Preparata-Hong 算法，按 x 坐标分成左右两半，分别求凸包再合并）。两者都是 O(n log n)。

三维凸包。 这一章也涉及了三维情况，算法更复杂。

第5章：邻近问题（Proximity）

这一章研究点集中"谁离谁最近""谁离谁最远"这类问题，核心是几种邻近图结构：

Voronoi图。 把平面分成若干区域，每个区域内的点都距离某个种子点最近。Voronoi图回答"最近邻居"问题。书中介绍了 Shamos-Hoey 的分治法构造 Voronoi 图，复杂度 O(n log n)。

Delaunay三角剖分。 Voronoi图的对偶图，连接相邻Voronoi区域的种子点得到。它是"最优三角剖分"，避免瘦长三角形。

凸包直径——旋转卡壳法（§5.4）。 这就是你标注的重点。问题很直观：给定一个凸多边形，找出距离最远的两个顶点。朴素方法是两两比较 n 个顶点，需要 O(n²)。Shamos 1978年的洞察是：

如果两条平行线从两侧夹住凸多边形并同步旋转360°，它们会依次"碰到"所有对踵点对（antipodal pairs）——即拥有平行支撑线的顶点对。而直径一定出现在某个对踵点对之间。

关键性质是：每个顶点最多成为2个对踵点对的成员，所以整个旋转过程只产生 O(n) 个对踵点对，全部检查一遍只需 O(n)。就像用一把卡尺（caliper）夹住多边形旋转一圈，"rotating calipers"这个名字由此而来  。

旋转卡壳法的直觉

想象把凸多边形放在两块平行的直尺中间，慢慢转动直尺360°。每次转动时，总有一个时刻两条直尺分别恰好碰到一个顶点——这就是一个对踵点对。整个过程就像用卡尺量遍多边形所有"最宽方向"，记录下最大宽度就是直径。

"rotating calipers"这个术语本身是 Godfried Toussaint 在1983年命名的  ，他把 Shamos 的原始思路推广到了更多几何问题（如凸多边形间距离、最小面积外接矩形等）。

这本书的地位

它是计算几何的第一本系统性教材，定义了这个领域的问题框架和方法论。后来的经典教材如 de Berg 等人的 Computational Geometry: Algorithms and Applications（1997）在很多方面是它的精神续作。

+ R: b! o" }  I

宏心

5 q9 G" b+ ?# G" d, X6 i8 _