查找三角形最大可能區域的最快方法

Question

假設我們在平面中有一組點，每個點都由一對整數座標描述。有沒有辦法在這個點上找到具有頂點的三角形，並且最大可能區域比O（n^3）算法更快？

Answer 1

1. 找到凸包。
2. 對於位於凸包上的點（A，B）的每個對，找到第三點C，給出三角形ABC的最大面積。這可以使用O（log n）中的二進制搜索完成。

要進行二分搜索，請按照某種順序（例如逆時針）排列凸包上的點。 A和B之間有兩個點序列，一個從A到B，另一個從B到A.分別考慮每個點。

二分查找步驟如下。在點間隔的中間連續三點C，C'，C「。計算CAB，C'AB，C''AB三個區域。如果C'是三者中最大的，那麼它是全球最大值，搜索結束。如果C最大，則最大值在間隔的左半部分。如果C'最大，則最大值在右半部分。 （編輯：注意，新的時間間隔應該在其中一端包含C'）。

那裏，一個算法在O（n^2 log n）中工作。

編輯2：this question的答案顯示瞭如何更快地做到這一點。你可以將兩種方法結合起來做更好的事情（在O（log n））中，在構造凸包之後，儘管它的構造仍然是O（n log n））。