減少閔可夫斯基差只有其船體的頂點？

Question

比方說，我們有兩個多面體，有沒有計算只有那些在閔可夫斯基差的船體頂點的任何effcient手段？

我知道拿到的單殼頂點你會發現在方向的一個多面體最遠的頂點，然後在方向上-A其他最遠的頂點。但是要做到這一點，每個頂點至少是O（N^2）。有沒有更高效的方法？

Answer 1

有計算凸多面體的Minkowski求和（並因此也差）的有效方法。它被描述爲例如here。它在兩個多面體的邊緣數量方面是線性的。因爲對於任何點集，它們的Minkowski和的凸包是它們凸包的Minkowski和，所以可以首先計算凸包（使用Chan的算法），然後執行Minkowski求和。