Massive Algorithms: Maximum Perimeter Triangle

Maximum Perimeter Triangle | Algorithms Notes

Given a set S of n points on plane, design an O( $n^2$ ) 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( $n^2)$ pairs of points and each pair takes O(n) time to find the maximum triangle, the total complexity is O( $n^3)$ . 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] = $\arg \max_k$ 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( $n^2$ ) 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( $n^2)$ 對點，而每一對點需要O(n)時間來找出最大邊長的三角形，總時間複雜度為O( $n^3)$ 。我們可以先計算出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] = $\arg \max_k$ 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( $n^2$ )。

Read full article from Maximum Perimeter Triangle | Algorithms Notes

Maximum Perimeter Triangle | Algorithms Notes

Labels

Popular Posts