凸包与凸壳

凸组合、凸包与下凸壳;支撑线和线性函数 Y-KX 的最小值在凸壳顶点取得。

标签 数学 / 凸包 / 凸壳 / 计算几何 / 线性函数

凸组合与凸包

本页只讨论平面有限点集。设 𝑃1,…,𝑃𝑚∈ℝ2。若

𝑃=∑𝑖=1𝑚𝜆𝑖𝑃𝑖,

其中 𝜆𝑖≥0 且 ∑𝑖𝜆𝑖=1,则称 𝑃 是这些点的凸组合。

集合 𝐶 是凸集,若对任意 𝑃,𝑄∈𝐶,线段 𝑃𝑄 都包含在 𝐶 中;等价地,𝐶 对有限凸组合封闭。

点集 𝑆 的凸包 conv(𝑆) 是包含 𝑆 的最小凸集,也等于 𝑆 的所有有限凸组合组成的集合。有限点集的凸包通常是凸多边形;所有点共线时退化为线段或点。凸包的顶点来自 𝑆,且不能写成 𝑆 中其他点的凸组合。

下凸壳与上凸壳

以下为简化讨论,假设最左点与最右点唯一,且没有重复横坐标。

把点按 𝑋 递增排序。凸包的边界可以分成从最左点到最右点的两条链:下侧链称为下凸壳,上侧链称为上凸壳。所有点都在下凸壳的上方或线上,也都在上凸壳的下方或线上。

不考虑共线点时,下凸壳各边的斜率严格递增,上凸壳各边的斜率严格递减。若三点共线,中间点不是凸包顶点,可以删去。

线性函数的最值

固定 𝐾,考虑

𝐿(𝑃)=𝑌−𝐾𝑋,𝑃=(𝑋,𝑌).

设

𝑏∗=min𝑃∈𝑆(𝑌−𝐾𝑋).

直线 ℓ:𝑦=𝐾𝑥+𝑏∗ 满足所有 𝑃∈𝑆 都在 ℓ 上方或线上,并且至少接触一个点。因此 ℓ 是点集的支撑线,接触点位于下凸壳;所以 𝐿 的最小值一定能在下凸壳上取得。

更一般地,凸多边形上的线性函数最小值在顶点取得。若 𝑃 是凸包内一点,它可以写成顶点的凸组合 𝑃=∑𝑖𝜆𝑖𝑃𝑖,于是

𝐿(𝑃)=∑𝑖𝜆𝑖𝐿(𝑃𝑖)≥min𝑖𝐿(𝑃𝑖).

所以只需检查顶点;若一条边上的函数值相同,两个端点都是最小值。最大值把 𝐿 换成 −𝐿,或看上凸壳。

支撑线与切线

若一条直线与凸包相交,且所有点都在这条直线的同一侧,称它为凸包的支撑线。支撑线与凸包的接触部分可以是一个顶点,也可以是一条边。这里说的“切线”是支撑线,不是微积分意义下的切线。

对固定的 𝐾,𝑦=𝐾𝑥+min(𝑌−𝐾𝑋) 是斜率为 𝐾 的支撑线。𝐾 增大时,下凸壳上的接触点从左向右移动;若接触一整条边,则两个端点都给出同一个最小值。这个单调性依赖于点按下凸壳的顺序排列;查询斜率不单调时不能直接移动指针。

方向与叉积

令 𝑢=𝐵−𝐴,𝑣=𝐶−𝐴。二维叉积定义为

𝑢×𝑣=𝑢𝑥𝑣𝑦−𝑢𝑦𝑣𝑥.

记

cross(𝐴,𝐵,𝐶)=𝑢×𝑣.

符号表示从 𝐴𝐵 转向 𝐴𝐶 的方向:正为左转,负为右转,零为共线。

按 𝑋 递增维护下凸壳时,连续三点的叉积应保持正;若小于等于零,中间点不在严格下凸壳上,可以删去。上凸壳的方向相反。坐标较大时,用叉积符号比较,不要用浮点斜率。

常见误解

  • 认为凸包和凸壳一定是两个不同对象:通常同义;下凸壳只是凸包的下侧边界。
  • 认为线性函数的最小值一定在唯一顶点取得:可能整条边取同值,端点都可选。
  • 认为上凸壳也能提供 𝑌−𝐾𝑋 的最小值:最小化看下凸壳,最大化看上凸壳。
  • 认为 𝐾 单调时切点一定严格移动:切点可以停在同一个顶点上,只保证单调不降。
  • 认为叉积为零的中间点必须保留:共线中间点对凸包没有贡献,通常删去。
  • 认为把点按 𝑋 排序并连起来就是下凸壳:还要删除不满足左转的点。
源码位置