Not sure how to crack this one. But I'd start with a Delaunay triangulation of A and count the points inside each triangle. Now we want to maximise either area (2D right, volume was a slip?) or point count, over a convex subset.
Now each triangle is convex. We mark any with more than n points as "bad", however we assign points, these triangles can't be included. The rest are candidates. For each candidate, go to its neighbours, and try to grow it. So we get roughly 3 * the number of triangles as composite quad candidates, and each successfully grown triangles is no longer a candidate, but still not "bad". All the quads must be convex. If a triangle fails to grow at all, it is still a "candidate", but it is "finished". As soon as a better candidate emerges, it is no longer a candidate and becomes "bad", no successful set may include it.
Now for the next stage, it's the same basic idea, try to unite with all possible neighbours, and eliminate from the candidate list anything you absorb. If you can't grow successfully, you become "finished". But you can't just unite with anybody, if not convex, you have to add extra triangles to become convex.
Eventually all of our candidates will either be absorbed or "finished",and we have a winner.
The question is whether this algorithm will create an exponential explosion of candidates or if we can eliminate them quickly enough to prevent that happening. I don't know the answer to that. But I think that if you try to unite with the larger neighbours first, you can pretty quickly eliminate most of the possible sub-sets.
