The problem is Given a set of points, determinate the Largest (in terms of area) Polygon consisting of at most $k$ points.
In a shape like The one below:
$k = 3,polygon =A,F,G $
I would like to know if there is a way to do this. (not choosing any $3\ldots k$ points and test)
For $k=3$ an algorithm as follows may help: Select two points, e.g. $A,B$. Determine the point farthest away from the line $AB$. That would be $F$, so now you have $ABF$. Drop the first point, so you have $B,F$. Determine the point farthest away from the line $BF$. That would be $G$, so now you have $BFG$. Drop the first point, so you now have $F,G$. Determine the point farthest away from the line $FG$. That would be $A$, so now you have $FGA$. If you continued further, you'd not get any improvement and stick with $FGA$.
Finding the point farthes away takes $O(n)$. If I'm not mistaken, a point may be rejected and selected again (as happened with $A$ above) at most twice, so the total running time is $O(n^2)$ and thus faster than $O(n^3)$ brute force.
I am not sure, however, how to generalize this to $k>3$.