algorithm - 凸多面体中体积最大的四面体

Question

给定一个凸多面体，我需要找到一个更快的算法来计算其中的最大体积四面体。我只能想到O（n ^ 4）的蛮力解决方案。我在想，如果我们可以使用一些预处理在不到 O(n) 时间内从使用 3 个多面体顶点形成的三角形中找到凸多面体中最远的顶点。这个四面体的体积将在这个三角形底下最大（四面体的体积是 1/3*底面积*高），对所有三角形执行此操作将使我在小于 O(n^4) 的时间内获得最大体积四面体。

Answer 1

我希望这个概率算法给出一个体积至少接近最大可能值的四面体，并且概率很高：

1. A,B,C从多面体中选择任意三个（成对不同的）顶点
2. 从多面体中选择一个点D，使四面体的体积最大化ABCD。
3. 从多面体中选择一个点A'，使四面体的体积最大化A'BCD
4. 从多面体中选择一个点B'，使四面体的体积最大化A'B'CD
5. 从多面体中选择一个点C'，使四面体的体积最大化A'B'C'D
6. ifA==A'和B==B'andC==C'停止回答ABCD。
7. 设置A=A', B=B',C=C'并在 2 处继续。

显然，该算法终止于任何有限多面体和 A、B、C 的任何初始选择。如果多面体不是“太对称”，算法应该很快终止（< O(n^2)）。

现在多次运行该算法（在步骤 1 中随机选择不同的 A、B、C。）并保持迄今为止发现的最大四面体将增加接近或达到最大可能体积的概率。