# Given the set of length of triangle, find the Maximum Area Triangle

Suppose we are given an array of numbers representing lengths of line segments. Find which three of these segments can be assembled into a triangle with maximum area.

I can compute the areas of all $O(n^3)$ possible triangles in $O(n^3)$ time using Heron's formula, and then return the largest. Can this be improved to $O(n^2)$ time? Or even faster?

• Is it possible that all the points you care about lie on the convex hull?
– Brannon
Nov 26 '13 at 1:11
• Cross-posted to Stack Overflow. Please do not post the same question to more than one Stack Exchange site as it wastes people's time when they work on the answer to a question that's already been answered somewhere else. Nov 27 '13 at 8:29

There is an $O(n^2)$ algorithm. By Heron's formula, the area of a triangle whose sides have length $a$, $b$, and $c$ is $S = \frac{1}{4}\sqrt{4a^2b^2 - (a^2+b^2-c^2)^2}$. Thus if we fix $a$ and $b$, the area is maximized when $c$ is closest to $\sqrt{a^2+b^2}$. A simple approach is to try all $O(n^2)$ possible pairs of $a$ and $b$ and perform binary search for the best value of $c$. This approach yields an $O(n^2 \log n)$ algorithm.

To achieve $O(n^2)$, we first sort the lengths of line segments ($l_1, l_2,\ldots, l_n$) in non-decreasing order. Let $a = l_i$ and $b = l_j$ with $i < j$, and let $k$ be the position in which $l_k$ is closest to $\sqrt{l_i^2 + l_j^2}$. When $j$ runs from $i+1$ to $n$, $k$ also increases gradually to $n$. Thus finding $k$ has an $O(1)$ amortized run time, i.e., the whole algorithm takes $O(n^2)$.

Update 11/26/2013:

An easier $O(n \log n)$ algorithm is to sort $l_i$ in a non-decreasing order, and find $3\leq k \leq n$ that maximizes the area of the triangle assembled from $l_{k-2}, l_{k-1}$, and $l_{k}$. It follows from the fact that if $i ,j < k$ then $S(l_i, l_j, l_k) \leq S(l_{k-2}, l_{k-1}, l_k)$ (can be proved by taking the derivative of $S$ and that $l_k$ is the length of the longest side).

• Are you sure you have Heron's formula correct? The closest match to your formula in the Wikipedia article is $\frac{1}{4}\sqrt{4a^2b^2-(a^2+b^2-c^2)^2}$. I think your reasoning works equally well for this formula, though.
– David Eppstein
Nov 26 '13 at 7:56
• @DavidEppstein Thank you for pointing out. I have updated the formula. It does not affect the correctness of the algorithm though.
– Thang Dinh
Nov 26 '13 at 8:11
• @DavidRicherby: I edited my answer 10' before Gustavoamigo posted his (Hover over the "edited xx hours ago" and "answered xx hours ago" to see the exact timestamp). Indeed, Gustavoamigo's answer is better, since it points out the condition for early termination ($c^2 \leq a^2 + b^2$). But why am I defending my answer?
– Thang Dinh
Nov 27 '13 at 14:04

I'll give the same answer I did on Stackoverflow.

I believe you can solve this problem in linear time, except that you will have to order your set of triangle length first, which is $\Theta(n\cdot \log n)$.

Here's how I would do it.

PSEUDO-CODE:

// V is the set of length of triangle.

Order(V)

// Heron Formula
define A(a,b,c) = SQRT(4a^2*b^2 - (a^2 + b^2 - c^2) ^2) / 4

// I is the last position in V
I := V.length - 1

// T(I) is the area of Maximum Area Triangle
T(I) =
if V[I]^2 <= V[I-1]^2+V[I-2]ˆ2
then return A(V[I-2],V[I-1],V[I])
else
return MAX( A(V[I-2],V[I-1],V[I]), T(I-1) )


Explanation: Assuming that $a \le b \le c$, when $c^2\le a^2+b^2$, if you increase any of the variable (a, b or c), you will have a triangle that has a larger area. So, if you peak the three largest numbers and the equation $c^2\le a^2+b^2$ is true, that means you have found the largest area. But, if $c^2\le a^2+b^2$ is not true, that is $c^2>a^2+b^2$, then a triangle with a different setup might have a greater area. If we change $b$ or $a$ with a lower value, we will have lower area, so that is not an option. So, the only option we have is to choose a different value for $c$, which is $T(I-1)$, which is also a recursion. The maximum value between $A(V[I-2],V[I-1],V[I])$ and $T(I-1)$ will be your answer.