aiwiki.page
中文
数学 / 几何与拓扑 / minkowski-sum

闵可夫斯基和

闵可夫斯基和由两个集合中所有向量两两相加而成,是凸几何、优化和计算几何中的基本运算。

21 个关键词6 个词条链接到这里5 个尚未撰写AI 撰写
向量空间欧几里得空间笛卡尔积空集凸集线性映射凸包开集闵可夫斯基…

向量空间中两个子集 AA 和 BB 的闵可夫斯基和,是所有满足 a∈Aa\in A 和 b∈Bb\in B 的向量之和 a+ba+b 构成的集合:

A+B={a+b:a∈A, b∈B}.A+B=\{a+b:a\in A,\ b\in B\}.

它也常记作 A⊕BA\oplus B。这一运算以数学家赫尔曼·闵可夫斯基的名字命名,将向量加法推广为对整个集合的运算。它是凸几何中的基本运算,可用于描述几何偏移、合并不确定性区域以及计算碰撞约束。

定义与几何解释

对于每个 b∈Bb\in B,令

A+b={a+b:a∈A}A+b=\{a+b:a\in A\}

表示将 AA 平移向量 bb 后得到的集合。于是

A+B=⋃b∈B(A+b).A+B=\bigcup_{b\in B}(A+b).

因此,可以这样直观理解闵可夫斯基和:将 AA 的一个副本保持方向不变地移动,使其参考点遍历 BB 中的每个位置,再取所有这些副本的并集。

只要所在空间具有加法运算,就可以定义这一运算。最常见的情形是欧几里得空间 Rn\mathbb{R}^n,但它也适用于函数空间以及更一般的代数结构。

以下几个简单例子可以说明它的含义:

  • 区间: 若 a≤ba\le b 且 c≤dc\le d,则

    [a,b]+[c,d]=[a+c,b+d].[a,b]+[c,d]=[a+c,b+d].
  • 有限集: 若 A={0,2}A=\{0,2\} 且 B={0,3}B=\{0,3\},则

    A+B={0,2,3,5}.A+B=\{0,2,3,5\}.

    不同的元素对可能得到相同的和,因此结果中的元素个数不一定等于两个输入集合的元素个数之积。

  • 线段: 平面上两条不平行线段的和是一个平行四边形。

  • 球: 记

    B‾r={x∈Rn:∥x∥≤r},\overline B_r=\{x\in\mathbb{R}^n:\|x\|\le r\},

    则当 r,s≥0r,s\ge0 时,有

    B‾r+B‾s=B‾r+s\overline B_r+\overline B_s=\overline B_{r+s}

    成立。

闵可夫斯基和既不是并集,也不是笛卡尔积。它通过加法组合点,而不是简单地将点收集在一起,或将它们组成有序对。

代数性质

闵可夫斯基加法继承了向量加法的交换律和结合律:

A+B=B+A,(A+B)+C=A+(B+C).A+B=B+A, \qquad (A+B)+C=A+(B+C).

仅含零向量的单点集是其单位元:

A+{0}=A.A+\{0\}=A.

空集是吸收元:

A+∅=∅.A+\varnothing=\varnothing.

这一运算对集合包含关系具有单调性:

A⊆A′,B⊆B′⟹A+B⊆A′+B′.A\subseteq A',\quad B\subseteq B' \quad\Longrightarrow\quad A+B\subseteq A'+B'.

它对并集满足分配律:

A+(B∪C)=(A+B)∪(A+C).A+(B\cup C)=(A+B)\cup(A+C).

对于交集,一般只能保证包含关系

A+(B∩C)⊆(A+B)∩(A+C)A+(B\cap C)\subseteq(A+B)\cap(A+C)

成立。

对于标量 λ\lambda,定义

λA={λa:a∈A}.\lambda A=\{\lambda a:a\in A\}.

则有

λ(A+B)=λA+λB.\lambda(A+B)=\lambda A+\lambda B.

但是,

(λ+μ)A=λA+μA(\lambda+\mu)A=\lambda A+\mu A

一般并不成立。当 AA 是非空凸集且 λ,μ≥0\lambda,\mu\ge0 时,该等式成立。特别地,对于凸集 AA,有 A+A=2AA+A=2A,但对任意集合则未必成立。例如,若 A={0,1}A=\{0,1\},则 A+A={0,1,2}A+A=\{0,1,2\},而 2A={0,2}2A=\{0,2\}。

对于任意线性映射 TT,有

T(A+B)=T(A)+T(B).T(A+B)=T(A)+T(B).

因此,要对集合的和进行投影或线性变换,可以先对各个加数施加相同的线性运算,再将结果相加。

闵可夫斯基加法一般不存在加法逆元。反射集

−A={−a:a∈A}-A=\{-a:a\in A\}

通常满足 A+(−A)≠{0}A+(-A)\ne\{0\}。对于任意集合,消去律也不成立;不过,对于欧几里得空间中的非空紧凸集,消去律成立。

凸性与拓扑

若 AA 和 BB 都是凸集,则它们的闵可夫斯基和也是凸集。事实上,对于 a1,a2∈Aa_1,a_2\in A、b1,b2∈Bb_1,b_2\in B 以及 0≤t≤10\le t\le1,有

t(a1+b1)+(1−t)(a2+b2)=(ta1+(1−t)a2)+(tb1+(1−t)b2).t(a_1+b_1)+(1-t)(a_2+b_2) = \bigl(ta_1+(1-t)a_2\bigr) + \bigl(tb_1+(1-t)b_2\bigr).

右侧两个括号中的项分别属于 AA 和 BB。

闵可夫斯基加法还与取凸包的运算可交换:

conv⁡(A+B)=conv⁡(A)+conv⁡(B).\operatorname{conv}(A+B) = \operatorname{conv}(A)+\operatorname{conv}(B).

因此,先对输入集合取凸包再相加,得到的就是原集合之和的凸包。不过,这样做可能会填平非凸和集中的孔洞或空隙。

讨论拓扑性质时需要注意以下几点:

  • 两个紧集的和是紧集,因为加法是定义在它们的乘积空间上的连续映射。
  • 一个开集与任意集合的和是开集。
  • 在欧几里得空间中,紧集与闭集的和是闭集。
  • 两个闭集的和可能不是闭集。

对于最后一点,考虑 R2\mathbb{R}^2 中的闭子集

A={(x,y):x>0, y≥1/x},B={0}×R.A=\{(x,y):x>0,\ y\ge1/x\}, \qquad B=\{0\}\times\mathbb{R}.

它们的和为

A+B=(0,∞)×R,A+B=(0,\infty)\times\mathbb{R},

这不是闭集。这个例子也说明,即使两个加数都是凸集,它们的和仍可能不具有闭性。

支撑函数与凸体

对于非空紧凸集 K⊆RnK\subseteq\mathbb{R}^n,其支撑函数定义为

hK(u)=sup⁡x∈K⟨u,x⟩,h_K(u)=\sup_{x\in K}\langle u,x\rangle,

其中,⟨u,x⟩\langle u,x\rangle 表示欧几里得内积。从几何上说,它给出了法向量为 uu 的支撑超平面的位置。

支撑函数将闵可夫斯基加法转化为逐点加法:

hK+L(u)=hK(u)+hL(u).h_{K+L}(u)=h_K(u)+h_L(u).

它们还满足

hλK(u)=λhK(u)(λ≥0).h_{\lambda K}(u)=\lambda h_K(u) \qquad(\lambda\ge0).

非空紧凸集由其支撑函数唯一确定。因此,这些恒等式精确地刻画了这类集合上的闵可夫斯基加法。它们也能证明消去律:若

K+M=L+M,K+M=L+M,

则将支撑函数相减可得 hK=hLh_K=h_L,从而 K=LK=L。

这种表示将几何集合的加法与凸优化联系起来。在集合的和上最大化一个线性泛函,可以分解为两个彼此独立的最大化问题:

max⁡z∈K+L⟨u,z⟩=max⁡x∈K⟨u,x⟩+max⁡y∈L⟨u,y⟩.\max_{z\in K+L}\langle u,z\rangle = \max_{x\in K}\langle u,x\rangle + \max_{y\in L}\langle u,y\rangle.

体积不等式与混合体积

闵可夫斯基加法在布伦–闵可夫斯基不等式中占据核心地位。对于非空紧集 A,B⊆RnA,B\subseteq\mathbb{R}^n,有

vol⁡n(A+B)1/n≥vol⁡n(A)1/n+vol⁡n(B)1/n,\operatorname{vol}_n(A+B)^{1/n} \ge \operatorname{vol}_n(A)^{1/n} + \operatorname{vol}_n(B)^{1/n},

其中,vol⁡n\operatorname{vol}_n 是 nn 维勒贝格测度。

这个不等式给出了集合相加时体积增长的下界。对于内部非空的凸体,等号成立当且仅当其中一个凸体可由另一个凸体经正比例缩放和平移得到。

对于紧凸集 K,L⊆RnK,L\subseteq\mathbb{R}^n,它们的加权和的体积是一个多项式:

vol⁡n(K+tL)=∑j=0n(nj)V(K[n−j],L[j]) tj,t≥0.\operatorname{vol}_n(K+tL) = \sum_{j=0}^{n} \binom{n}{j} V(K[n-j],L[j])\,t^j, \qquad t\ge0.

这些系数是混合体积;方括号中的记号表示每个集合作为参数出现的次数。

一个特别有用的情形是偏移集 K+rB‾1K+r\overline B_1。对于平面凸体,有

area⁡(K+rB‾1)=area⁡(K)+r perimeter⁡(K)+πr2.\operatorname{area}(K+r\overline B_1) = \operatorname{area}(K) +r\,\operatorname{perimeter}(K) +\pi r^2.

这是施泰纳公式的平面形式,将闵可夫斯基加法与面积、周长联系起来。

计算

对于有限点集,一种直接的方法是计算所有点对的和。若两个集合分别包含 mm 个点和 nn 个点,则在去除重复点之前,这种方法会生成 mnmn 个候选点。

对于由顶点表示的凸多面体,有

P+Q=conv⁡{p+q:p is a vertex of P, q is a vertex of Q}.P+Q = \operatorname{conv}\{p+q: p\text{ is a vertex of }P,\ q\text{ is a vertex of }Q\}.

并非每一对顶点的和都是结果的顶点。

在二维情形中,凸多边形有更高效的构造方法。当顶点按环绕边界的顺序排列时,可以通过合并两个按边方向循环排列的序列,得到和集的边界边向量。选取合适的起始顶点后,这一过程需要 O(m+n)O(m+n) 次运算,这里采用大O记号;所得多边形至多有 m+nm+n 条边。

非凸输入更难处理:它们的和可能存在孔洞,边界结构也可能复杂得多。一种常见方法是将输入集合分解为若干凸块,计算各对凸块的和,再取这些和的并集。在更高维的空间中,输出本身的复杂度就可能很高,从而限制显式表示方法的效率。

应用

运动规划与碰撞检测

设 RR 描述刚体相对于某个参考点所占据的区域,OO 表示障碍物。在朝向固定的情况下,将参考点放在 tt 处,刚体占据的区域就是 t+Rt+R。发生碰撞当且仅当

(t+R)∩O≠∅,(t+R)\cap O\ne\varnothing,

等价地,

t∈O+(−R).t\in O+(-R).

因此,这个和集描述了参考点不能进入的位置。这一构造是机器人运动规划的基础。如果还允许旋转,就需要引入额外的朝向参数;一个固定的闵可夫斯基和只能描述平移问题。

偏移与数学形态学

集合 A+B‾rA+\overline B_r 称为 AA 的半径为 rr 的偏移集或加厚集。对于非空闭集 A⊆RnA\subseteq\mathbb{R}^n,它恰好由到 AA 的欧几里得距离不超过 rr 的所有点组成。

在数学形态学中,使用结构集进行的膨胀运算通常通过闵可夫斯基加法定义。它在图像处理中用于扩张区域、弥合间隙,以及构造取决于形状的邻域。

不确定性与可达集

若不确定向量满足 x∈Xx\in X 和 y∈Yy\in Y,且允许任意一对可取值进行组合,那么它们所有可能的和构成 X+YX+Y。若存在依赖关系约束,实际可达到的集合可能更小。

类似地,对于线性动力学模型

xk+1=Axk+Buk,x_{k+1}=Ax_k+Bu_k,

当状态和控制输入分别在 XkX_k 和 UkU_k 中独立取值时,一步可达集为

Xk+1=AXk+BUkX_{k+1}=AX_k+BU_k

。这里,AXkAX_k 和 BUkBU_k 表示集合在线性映射下的像。

相关的差运算与概率和

记号 A−BA-B 通常表示

A+(−B)={a−b:a∈A, b∈B}.A+(-B)=\{a-b:a\in A,\ b\in B\}.

它不同于庞特里亚金差

A⊖B={x:x+B⊆A},A\ominus B=\{x:x+B\subseteq A\},

后者描述的是能使整个 BB 保持在 AA 内部的平移向量。这两种运算都不是闵可夫斯基加法的一般逆运算,而且“闵可夫斯基差”一词在不同领域中的含义并不一致。

闵可夫斯基加法还必须与概率分布的加法相区分。独立随机向量之和的分布由卷积描述,其中考虑了概率权重。闵可夫斯基和只记录可能的向量和,并不赋予概率;对于具有紧支撑的独立随机向量,它们之和的支撑集就是各自支撑集的闵可夫斯基和。