如何证明凸包最小面积外接矩形包含最小距离轨迹的两条边

已知条件 #

• 凸包最小距离轨迹生成规则：遍历凸包所有边，计算每条边对应的凸包上最远点距离，取所有距离的最小值d_min，记对应边为E0，对应最远点为P_max，过P_max作E0的平行线E1，E0与E1之间的带状区域即为最小距离轨迹。
• 凸包最小面积外接矩形定义：可完整包围凸包所有顶点、边的所有朝向矩形中，面积最小的那一个，旋转卡壳算法已验证：任意凸包的最小面积外接矩形必然有一条边与凸包的某条边重合。

可行证明思路 #

步骤1：证明最小面积外接矩形必然包含E0与E1两条边 #

1. 首先由最小距离轨迹的定义可知，d_min是凸包所有边对应最远点距离的最小值，也就是凸包的最小宽度，E0与E1分别是最小宽度对应的两条边界线。
2. 假设最小面积外接矩形与凸包重合的边是E0：此时矩形与E0平行的对边必须经过凸包上到E0最远的点P_max才能保证刚好包围凸包，也就是对边与E1完全重合，此时矩形的一组对边恰好是最小距离轨迹的两条边界，满足共边要求。
3. 假设最小面积外接矩形与凸包重合的边不是E0，记该边为Ex，Ex对应的最远点距离为dx：根据d_min的定义，dx ≥ d_min。此时该矩形面积为Sx = Lx * dx，其中Lx为矩形沿Ex方向的长度。如果我们将矩形旋转到与E0平行的朝向，此时矩形面积为S0 = L0 * d_min，由于d_min是凸包所有方向宽度的最小值，S0必然小于等于Sx，与Sx是最小面积的前提矛盾，因此该假设不成立。

步骤2：证明该矩形必然包含凸包所有点 #

最小外接矩形的定义本身就要求其完整包围凸包所有顶点与边，因此该性质自然成立。 #

示意图 #

• 最小距离轨迹示例：
  
• 凸包最小外接矩形示例：
  

内容的提问来源于stack exchange，提问作者Projekat Pr