# Largest Quadrilateral from a Set of Points

I posted the below on StackOverflow but was directed here as this may be more mathematical problem but I was looking to implement an algorithm....

I have a discrete set of points.

From this set of point I need to find the 4 points that make up a Quadrilateral with the largest area.

To begin I have already used a Gift Wrapping algorithm to establish the points that make up the convex hull as the 4 points of the Quad will be on the hull.

I am now looking at what would be the best way to establish if the convex hull consists of more than 4 points how to narrow this down to only 4 points that make up that Quad.

I can only think of a brute force method of checking the area or perimeter of each combination of 4 points to then pick up the set with the largest but as the number of points on the convex hull is not predetermined I want to hopefully find a more efficient method.

I don't mind using brute force but was hoping someone could think up something a little more elegant to implement.

Found this entry:

Suppose you have $n$ points on the convex hull. Suppose there was a point $P_0$ which you knew to be part of the largest quad. Moving along the hull to other points will mean cutting off parts of the convex hull. A step to the next hull vertex cuts away nothing, skipping one vertex and using the one after taht will cut away a triangle, and so on. You can conceive this cut-away area as a kind of cost. So your task is one of finding a path consisting of four steps and going from $P_0$ to $P_n$ (which is identical to $P_0$ in its position). You could use dynamic programming for this. With a bit of tweaking, it should be possible to not rely on the starting point, but compute minimal cost cycles of length 4 for any pair. In general I'd worry about going around the hull more than once, but since that would lead to a smaller area, I doubt it's going to cause trouble in your case.