Just a quick heuristic idea:
Step 1) I would start with determining the convex hull of the original set of points in $\mathcal O(n \log n)$ with the Graham scan. There are various implementations out there (in many languages). Robert Sedgewick has one in its book Algorithms (1983). The Java Version can be found here.
Step 2) Then I would remove the points defining the incumbent hull and determine the convex hull of the remaining points. Afterwards I would merge the incumbent hull and convex hull following a greedy approach, i.e. I would check for each pair of points whether the area defining the hull decreases and if the resulting hull still is a hull.
This approach limits the points to consider in each step and hopefully allows to determine good solutions.
One can repeat step 2 multiple times.