旋转卡壳与凸多边形直径

两条平行尺贴在凸多边形外面。旋转它们时，接触点沿边界按同一个方向走，不会倒退。一个支撑方向在一条边的法向处发生事件；此刻至少一把尺贴住整条边，另一把尺落在一个顶点或另一条平行边上。

所有需要考虑的对踵顶点对都出现在这些接触变化附近。因此每条边只需要看它对面的最高点，并把边的两个端点都纳入距离比较。最高点最大化的是到直线的垂距，不是到某个固定端点的距离，所以最后这一步不能省略。

取逆时针六边形

分别编号 $0,\dots ,5$。随着边 $i=0,1,\dots ,5$ 前进，对面最高点的编号可以依次取

这里 $5\to 1$ 是跨过编号零继续向前，不是指针退回。把循环序列展开后，每次支撑接触都沿同一方向移动。

第一条边 $p_0{p}_1$ 的对面点为 $p_3=(6,2)$。两个候选平方距离为

其余边事件都没有超过 $50$，所以直径为 $\sqrt{50}$。穷举全部十五对顶点也给出相同结果。核验程序使用平方距离比较，直到输出长度时才开平方，避免无关的浮点舍入。

矩形体现平局边界。一条边的对面也是一整条平行边，两个对面端点等高，真正的直径却是对角线。如果算法在等高时只比较任意一个端点组合，可能漏掉另一条最大对角线，甚至因候选实现不完整而漏掉最大值。实现要么显式枚举平行边的四种端点配对，要么证明其等价平局处理覆盖这些候选。

输入若有连续共线点，先压成真正极点可简化支撑接触；若还要返回所有达到最大值的原输入索引，再用保留的边界映射恢复。全共线点集的凸包是一条线段，答案直接是两端距离；单点和空集应有自己的接口，不能硬进入循环卡壳。

凸性使对面接触单调前进。按上述首边初始化后，初始化和整圈推进合计不超过常数倍 $h$ 次；每条边还做常数次平局比较。用摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。，整个阶段时间为 $O(h)$、额外空间 $O(1)$，输出全部平局点对时另计输出大小。

若原输入是 $n$ 个无序点，端到端成本还包括凸包构造；不能把 $O(h)$ 卡壳阶段写成任意点集的线性直径算法。所有面积比较可由精确方向谓词公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。完成，整型坐标的平方距离可能比原坐标需要更多位数。

最近点对公理库平面最近点对Closest pair of points · Planar closest pair以分治和窄带 packing 证书在 O(n log n) 时间求 Euclidean 平面最近点对。依靠局部稀疏条带，而直径由凸包边界与全局支撑控制。旋转卡壳也可用于宽度或最小包围矩形，但目标函数和需要同步的支撑线数量会改变；“都能旋转”不是这些算法共享同一候选公式的理由。