Suppose points are given in the form (a1, b1) (a2, b2)..... (an, bn).
- find the point furthest away from the origin by maximizing a^2 +
b^2 [ will take O(n) time]
- Find the point at maximum distance from this point. Use distance
formula. Sqrt( (a2-a1)^2 + (b2-b1)^2) [will take O(n) time]
- Find third point by maximizing the perimeter. We already have the
length of one side obtained from the distance formula above.
Repeat the same procedure for the other two
sides. [will take O(n) time]
These three points should form a triangle with max. area. (Max.
perimeter, (please correct me if I'm wrong) = Max. area.)
I chose to use perimeter as it's quicker to calculate than area (= 1/2
*b * h, where h will have to be calculated).
This should run in O(n) time. I've tried thinking of scenarios where
this algorithm will not yield the max. area, but can't
seem to find such a case. If you think this won't work or isn't
optimum, please present such a case.
-Minotauraus.
On Jun 14, 4:27 am, amit <[email protected]> wrote:
> Given N points how can we find a triangle formed using any of the
> three points with maximum area?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
