如何在蛮力搜索之外找到凸包中的最大三角形

Question

给定凸多边形,如何找到定义具有最大面积的三角形的3个点.

相关:该三角形的外接圆是否也会定义多边形的最小边界圆？

Answer 1

是的,你可以做得比蛮力更好.

通过蛮力,我认为你的意思是检查所有三点,并选择一个最大面积的点.这在O(n ³)时间内运行,但事实证明,不仅可以在O(n ²)中进行,而且可以在O(n)时间内完成!

[ 更新: 2017年发表的一篇论文通过实例表明O(n)解决方案不适用于特定类别的多边形.有关详细信息,请参阅此答案.但是O(n ²)算法仍然是正确的.

通过首先对点进行排序/计算凸包(在O(n log n)时间内),如果需要,我们可以假设我们有凸多边形/船体,其点按照它们在多边形中出现的顺序循环排序.调用点1,2,3,...,n.令(变量)点A,B和C分别从1,2和3开始(以循环次序).我们将移动A,B,C直到ABC是最大面积三角形.(这个想法类似于旋转卡尺方法,在计算直径(最远的一对)时使用.)

在A和B固定的情况下,提前C(例如,最初,A = 1,B = 2,C前进到C = 3,C = 4,...),只要三角形的面积增加,即,只要面积(A,B,C)≤面积(A,B,C + 1).这个点C将是那些固定的A和B最大化区域(ABC)的点.(换句话说,函数Area(ABC)是C的函数的单峰).)

接下来,如果增加面积,则前进B(不改变A和C).如果是这样,再次按上述方式推进C. 然后如果可能的话再次前进B等.这将给出最大区域三角形,其中A作为顶点之一.

(到此为止的部分应该很容易证明,并且对每个A单独执行此操作将给出O(n ²)算法.)

现在再次推进A,如果它改善了面积,等等._{(这部分的正确性更加微妙:Dobkin和Snyder在他们的论文中给出了证据,但是最近的一篇论文显示了一个反例.我还没有理解它.)}

虽然这有三个"嵌套"循环,但请注意B和C总是向前推进,并且它们总共最多前进2n次(类似A最多前进n次),因此整个过程在O(n)时间内运行.

Python中的代码片段(转换为C应该是直截了当的):

 # Assume points have been sorted already, as 0...(n-1)
 A = 0; B = 1; C = 2
 bA= A; bB= B; bC= C #The "best" triple of points
 while True: #loop A

   while True: #loop B
     while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
       C = (C+1)%n
     if area(A, B, C) <= area(A, (B+1)%n, C): 
       B = (B+1)%n
       continue
     else:
       break

   if area(A, B, C) > area(bA, bB, bC):
     bA = A; bB = B; bC = C

   A = (A+1)%n
   if A==B: B = (B+1)%n
   if B==C: C = (C+1)%n
   if A==0: break

该算法在Dobkin和Snyder中得到证明,在一种最大化和最小化某些几何问题的一般方法中,FOCS 1979,上面的代码是他们的ALGOL-60代码的直接翻译.为休息时间结构道歉; 应该可以将它们转换为更简单的while循环.

Answer 2

根据这篇论文，有一类凸多边形，其中 ShreevatsaR 的答案引用的算法失败。论文还提出了一种 O(n log n) 分治算法来解决该问题。

显然，为所有A移动 B 点和 C 点的更简单的 O(n ² ) 算法仍然有效。