The fastest way to find the greatest possible area of triangle

Question

Let's imagine that we have a set of points in the plane, each described by pair of integer coordinates. Is there a way to find the triangle with vertices on this points with the greatest possible area faster than by O(n^3) algorithm?

Answer 1

1. Find the convex hull.
2. For each pair of points (A, B) lying on the convex hull, find the third point C giving the maximal area to the triangle ABC. This can be done using binary search in O(log n).

To do the binary search, arrange points on the convex hull going in some order (e.g. counterclockwise). There are two sequences of points between A and B, one is going from A to B and the other from B to A. Consider each one separately.

The binary search step is as follows. Take three consecutive points C, C', C'' in the middle of the interval of points. Compute three areas CAB, C'AB, C''AB. If C' is the largest of the three, it's the global maximum and the search is over. If C is the largest, the maximum is in the left half of the interval. If C'' is the largest, the maximum is in the right half. (Edit: note, the new interval should contain C' at one of the ends).

There, an algorithm that works in O(n^2 log n).

Edit 2: the answer to this question shows how to do it significantly faster. You can combine both approaches to do better yet (in O(log n) after the convex hull is built, though with the construction of the hull it's still O(n log n)).