给定一个凸多面体，我需要找到一个更快速的算法来计算它的最大体积四面体。我只能想到O（n^4）的蛮力解我在想，如果我们用一些预处理方法，在多面体上用3个顶点形成一个三角形，就能找到凸多面体中最远的顶点。这个四面体的体积将是最大的，这个三角形基（四面体的体积是1/3×基面积×高度），这样做对于所有的三角形都能给我最大值。体积四面体小于0（n^4）。
最佳答案
我希望这个概率算法能给出一个四面体，其体积至少接近最大可能值，概率很高：
从多面体中选择任意三个（成对不同的）顶点A,B,C。
从多面体中选择一个点，使四面体的体积最大化。
从多面体中选择一个点D使四面体的体积最大化ABCD
从多面体中选择一个点A'使四面体的体积最大化A'BCD
从多面体中选择一个点B'使四面体的体积最大化A'B'CD
如果C'和A'B'C'D和A==A'停止回答B==B'。
设置C==C'，ABCD，A=A'并在2继续。
显然，该算法终止于任何有限多面体以及a、b、c的任何初始选择。如果多面体不是“太对称”，则该算法应快速终止（<B=B'）。
现在运行这个算法数次（在步骤1中有不同的A、B、C的随机选择），并且保持到目前为止发现的最大四面体将增加接近或到达最大可能体积的概率。