1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is it possible that all the points you care about lie on the convex hull? $\endgroup$ – Brannon Nov 26 '13 at 1:11
  • 7
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 27 '13 at 8:29
7
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Nov 26 '13 at 7:56
  • $\begingroup$ @DavidEppstein Thank you for pointing out. I have updated the formula. It does not affect the correctness of the algorithm though. $\endgroup$ – Thang Dinh Nov 26 '13 at 8:11
  • 1
    $\begingroup$ @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? $\endgroup$ – Thang Dinh Nov 27 '13 at 14:04
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.