Maximum Enclosing Convex Polygon of a Given Area
It sounds like your problem is the following:


  Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.


This problem looks pretty tough to me, and I don't have a great algorithm for it, but I'll suggest two schemes.  The first solves a simplified version of this problem (for rectangles instead of arbitrary polygons), and the second is a heuristic algorithm that might or might not work "well enough" on real-world instances.

Simplified variant: rectangles

Suppose we focus on the easier case where $\mathcal{P}$ must be an axis-aligned rectangle.  Then I can give a $O(n^2 (\lg n)^2)$ time algorithm.

Without loss of generality, the $x$-coordinate of the left and right sides of this rectangle must agree with the $x$-coordinate of some pair of points, and similarly for the top and bottom sides.

So, guess the $x$-coordinate of the left side of the rectangle (there are $\le n$ possibilities), say $x_L$.  Now, do a binary search on the width of the rectangle (there are $\le n$ possibilities), using the following ideas.

Given a guess at the width $w$ of the rectangle, you can calculate the maximum number of points that can fit in an allowable rectangle with those $x$-coordinates for the left and right sides, as follows.  Start by filtering out all points whose $x$-coordinate is not in $[x_L,x_L+w]$.  Sort the remaining points by their $y$-axis.  Now look for the $y$-value $y_B$ for the bottom side of the rectangle, which maximizes the number of remaining points whose $y$-coordinate is in the range $[y_B,y_B+A/w]$.  This can be found with a straightforward linear scan of the remaining points (with two pointers advancing monotonically).

With this, given $x_L$, you can do a binary search for $w$.  Each guess at $w$ takes $O(n \lg n)$ work to compute the maximum number of points that can be fit into a rectangle of that sort.  Since there are $\le n$ possible values for $w$, you'll do $O(\lg n)$ iterations in the binary search.  Since there are $\le n$ possibilities for $x_L$, the overall running time is $O(n^2 (\lg n)^2)$.

Since a rectangle is a convex polygon, this gives you a lower bound on the number of points that can be covered by a convex polygon with area $\le A$.  It might not be an especially tight lower bound, but maybe it's a start.

Heuristic for arbitrary polygons

We could use branch-and-bound type techniques here.

Define a directed acyclic graph (dag), the search dag, where each vertex is a convex polyhedron $\mathcal{P}$ obtained as the convex hull of some subset of the $n$ points, and there is an edge from $\mathcal{P}$ to $\mathcal{Q}$ if there is some point $p_i$ not in $\mathcal{P}$ such that the convex hull of $\mathcal{P},p_i$ is $\mathcal{Q}$.  The root of this graph is the empty polyhedron, which covers no points.  Call any node of this graph that has no out-edges a "leaf".  The best polyhedron must be some leaf.

A naive approach would be to do a breadth-first search on this dag.  Unfortunately, the dag is probably exponential in size, so this naive approach will probably be too slow.

You might do better using branch-and-bound techniques.  Define the "quality" of a leaf in this graph to be the number of points covered by its associated polyhedron.  Also, define the "quality" of a node $x$ in this graph to be the maximum of the quality of all of the leaves that are reachable from $x$.  Of course, we cannot compute the quality of a node without exploring everything reachable from it (which is too expensive), but we can estimate it.

In particular, we can compute an upper bound on the quality of any given node.  This is enough to do branch-and-bound.  We basically iteratively explore the graph.  At each stage, we keep track of the "best" solution we've found so far: i.e., among all the polyhedron $\mathcal{P}$ corresponding to some node we've visited, keep track of the maximum number of points covered by any of these.  Say this number is $b$.  Now if we reach a node $x$ where our upper bound on its quality implies that the quality of $x$ is $\le b$, then we don't need to visit $x$ or any of its descendants.  This might help us reduce the search space.

How do we get an upper bound on the quality of a node?  Well, here's one way.  Suppose we have precomputed, for each $i=1,2,\dots,k$, the minimal area of any convex polygon that contains $i$ points, call it $\alpha(i)$.  Now if we have a node $x$ that corresponds to a polyhedron $\mathcal{P}_x$ of area $A_x$, and if $A_x+\alpha(i) &gt; A$, then here's an upper bound on the quality of $\mathcal{P}$: it must be at most the number of points contained in $\mathcal{P}$, plus $i-1$.  This could be a somewhat loose bound, but it is something.

How do we do the precomputation?  Well, that's basically an easier instance of the same problem, with a smaller value for $A$.  So, we can do the precomputation via a recursive or iterative application of this algorithm, for increasing values of $A$ (or via similar ideas).