凸包与凸壳
凸组合、凸包与下凸壳;支撑线和线性函数 Y-KX 的最小值在凸壳顶点取得。标签 数学 / 凸包 / 凸壳 / 计算几何 / 线性函数
凸组合与凸包
本页只讨论平面有限点集。设 。若
其中 且 ,则称 是这些点的凸组合。
集合 是凸集,若对任意 ,线段 都包含在 中;等价地, 对有限凸组合封闭。
点集 的凸包 是包含 的最小凸集,也等于 的所有有限凸组合组成的集合。有限点集的凸包通常是凸多边形;所有点共线时退化为线段或点。凸包的顶点来自 ,且不能写成 中其他点的凸组合。
下凸壳与上凸壳
以下为简化讨论,假设最左点与最右点唯一,且没有重复横坐标。
把点按 递增排序。凸包的边界可以分成从最左点到最右点的两条链:下侧链称为下凸壳,上侧链称为上凸壳。所有点都在下凸壳的上方或线上,也都在上凸壳的下方或线上。
不考虑共线点时,下凸壳各边的斜率严格递增,上凸壳各边的斜率严格递减。若三点共线,中间点不是凸包顶点,可以删去。
线性函数的最值
固定 ,考虑
设
直线 满足所有 都在 上方或线上,并且至少接触一个点。因此 是点集的支撑线,接触点位于下凸壳;所以 的最小值一定能在下凸壳上取得。
更一般地,凸多边形上的线性函数最小值在顶点取得。若 是凸包内一点,它可以写成顶点的凸组合 ,于是
所以只需检查顶点;若一条边上的函数值相同,两个端点都是最小值。最大值把 换成 ,或看上凸壳。
支撑线与切线
若一条直线与凸包相交,且所有点都在这条直线的同一侧,称它为凸包的支撑线。支撑线与凸包的接触部分可以是一个顶点,也可以是一条边。这里说的“切线”是支撑线,不是微积分意义下的切线。
对固定的 , 是斜率为 的支撑线。 增大时,下凸壳上的接触点从左向右移动;若接触一整条边,则两个端点都给出同一个最小值。这个单调性依赖于点按下凸壳的顺序排列;查询斜率不单调时不能直接移动指针。
方向与叉积
令 ,。二维叉积定义为
记
符号表示从 转向 的方向:正为左转,负为右转,零为共线。
按 递增维护下凸壳时,连续三点的叉积应保持正;若小于等于零,中间点不在严格下凸壳上,可以删去。上凸壳的方向相反。坐标较大时,用叉积符号比较,不要用浮点斜率。
常见误解
- 认为凸包和凸壳一定是两个不同对象:通常同义;下凸壳只是凸包的下侧边界。
- 认为线性函数的最小值一定在唯一顶点取得:可能整条边取同值,端点都可选。
- 认为上凸壳也能提供 的最小值:最小化看下凸壳,最大化看上凸壳。
- 认为 单调时切点一定严格移动:切点可以停在同一个顶点上,只保证单调不降。
- 认为叉积为零的中间点必须保留:共线中间点对凸包没有贡献,通常删去。
- 认为把点按 排序并连起来就是下凸壳:还要删除不满足左转的点。