0
$\begingroup$

Given a finite set of 2-d points, I need to find the maximum area of triangle formed.

My solution steps :

  1. Take mean of points , lets call it (x_m, y_m).
  2. Take 3 most distant points from (x_m, y_m).
  3. Area of triangle formed using these 3 points is the maximum possible area.

Is my solution correct? If not, what could be the cases where it gives wrong result?

$\endgroup$
1
$\begingroup$

A simple case of incorrect result:

We choose a million points around the unit circle.

We put three points very close together, but very far from the unit circle.

Those three points are what the algorithm would choose, but they would form a minuscule triangle.

When you can choose an equilateral triangle in the unit circle.

Or, better yet, you could choose a point in the far triangle and two points in the unit circle.

$\endgroup$
  • $\begingroup$ You could just make the far three points colinear. $\endgroup$ – Ennar Apr 22 at 9:03

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.