Is there an algorithm for this? It's okay if it's an approximation or adds further constraints to simplify. Here's a more detailed statement
I have K points in some low dimensional space (say 2d). Each one has a penalty (could be zero). And if it helps, we could restrict it so that there are only a few discrete penalty values rather than a continuum.
Given N, I want to find a convex region that contains exactly N of these points. The cost of a region is the sum of the penalties of all the points. We want to minimize this cost.
e.g., you must find a convex region of land with exactly N trees. Some trees are worse (higher penalty) than others, so you want to find the optimal such region.
Is there a known algorithm for this? It's okay if the solution is only approximately optimal. It would also be okay to only cover approximately N, but I don't want to relax this too much. Or, it would be okay to introduce some simplifying constraints, such as: the convex region must be a triangle (can only be defined by 3 points).
I suppose with the triangle constraint, I could do a brute force search on a random sample of the input points search of all possible triangles defined by 3 points, but this would be something like O(S^4) where S is my sample size. S^3 triangles and O(S) loop over points to check if they're in that triangle.
If n is not too large you could try integer programming. Enumerate all n choose 4 combinations of 4 points, filter out the combinations that don't have one point x1 inside the triangle formed by the other three x2, x3, x4, write a constraint
-x1 + x2 + x3 + x4 <= 2
for each combination, plus a cardinality constraint
sum_i x_i = n
and minimize
sum_i penalty_i x_i.