Maximum Perimeter Triangle | Algorithms Notes
Given a set S of n points on plane, design an O(
) time algorithm to find three points in S forming a triangle with the maximum perimeter.
Solution:
Let d(i, j) be the distance between i-th point and j-th point. For a pair of points (i, j), we want to determine k, such that d(i, k) + d(k, j) is maximized. Since there are O(
pairs of points and each pair takes O(n) time to find the maximum triangle, the total complexity is O(
. In order to speed-up, we compute a convex hull C of S, since only points in C can form maximum perimeter triangle. Without loss of generality, we assume S = C and the points are ordered counter-clockwise. We know that the distance between points in convex hull satisfies convex quadrangle inequality, that is d(i, k) + d(j, l) ≥ d(i, l) + d(j, k) for i ≤ j ≤ k ≤ l. Let K[i][j] = 
d(i, k) + d(k, j). By convex quadrangle inequality, K[i][j] ≤ K[i+1][j] ≤ K[i+1][j+1]. Consequently, we can compute all values K[i][j] diagonal by diagonal in O() time.
Note: The same approach can be generalized to find maximum perimeter k-gon for a given set of points.
解法：
令d(i, j)表示第i點與第j點之距離。對於一對點(i, j)來說，我們想要找出另一點k使得d(i, k) + d(k, j)最大。因為總共有O(對點，而每一對點需要O(n)時間來找出最大邊長的三角形，總時間複雜度為O(。我們可以先計算出S的convex hull C，因為只有在convex hull上的點才有可能形成最大邊長三角形。在不失一般性的情況下，我們假設S = C而且所有點都是按照逆時針順序排列。我們知道在convex hull上的距離滿足convex quadrangle inequality，即d(i, k) + d(j, l) ≥ d(i, l) + d(j, k)對於i ≤ j ≤ k ≤ l令K[i][j] = d(i, k) + d(k, j)，依照convex quadrangle inequality，我們知道K[i][j] ≤ K[i+1][j] ≤ K[i+1][j+1]。因此，我們可以按照對角線的順序來計算所有的K[i][j]。總時間複雜度為O()。
Read full article from Maximum Perimeter Triangle | Algorithms Notes
