闵可夫斯基和
发布时间
阅读量：
阅读量
之前在省赛和cf教育场都碰到了闵可夫斯基和这个东西，教育场的时候菜鸡小南瓜眼巴巴看着一堆人秒了这题却毫无想法，哭唧唧。于是在维基百科学习了一波之后来写一下。
定义
在几何中，两个点集S_1,S_2的闵可夫斯基和被定义为
S_1+S_2 = \{ a+b | a \in S_1,b \in S_2 \}
闵可夫斯基和的凸包
首先第一个性质，对于两个点集S_1,S_2，它们的闵可夫斯基和的凸包等于它们凸包的闵可夫斯基和，即
Conv(S_1+S_2) = Conv(S_1)+Conv(S_2)
同样扩展到多个点集也是这样的
Conv( \sum S_n) = \sum Conv(S_n))
那么为什么呢
对于两个凸包相加，我们可以看成一个凸包沿着另一个凸包转一圈之后形成的图形
比如我现在有个凸包A
然后我把凸包B放上去转一圈
把外面的点连起来就得到了两个凸包的闵可夫斯基和的凸包
那么这个得到的图形明显是个凸包（x对不起我不会证明
而之前在原凸包里面的点在取和之后也肯定在这个大凸包里面
所以就有了上面的结论
怎么求两个凸包的闵可夫斯基和
先上结论：把两个凸包的所有的边极角排序，然后依次相连就好了
是不是非常的鹅妹子嘤XD
这里试图给个证明：
最后得到的凸包，它的边分两种，一种是B凸包上的某个点沿着A凸包的某一条边平移得到的，另一种是B凸包的边直接作为外面凸包的边。
第一种边很明显A中的每条边都会出现一次，因为每条边被沿着走了一次
而第二种，B中的边在B转到A中一个点，并且A的前一条边极角比它小，后一条边极角比它大的时候，会成为一次大凸包上的边
因此A，B中所有的边都出现了一次
而凸包的边又是按极角排的
所以把A，B里面所有的边极角排序之后首尾相连就可以啦XD
全部评论 (0)
还没有任何评论哟~