Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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).
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.
