给定 2d space 中的一组点，每个点都有一些惩罚，找到一个恰好覆盖 N 个点的凸区域，最小化惩罚
Given set of points in 2d space, each with some penalty, find a convex region covering exactly N points, minimizing penalty
有算法吗？如果它是一个近似值或者添加进一步的约束来简化也没关系。这里有更详细的说法
我在一些低维 space（比如 2d）中有 K 个点。每个人都有一个惩罚（可以是零）。如果有帮助，我们可以限制它，以便只有几个离散的惩罚值，而不是一个连续体。
给定 N，我想找到一个恰好包含 N 个这些点的凸区域。一个区域的代价是所有点的惩罚之和。我们希望将此成本降至最低。
例如，你必须找到一个恰好有 N 棵树的凸区域。有些树比其他树更差（更高的惩罚），所以你想找到最佳的这样的区域。
是否有已知的算法？如果解决方案只是近似最优也没关系。只覆盖大约 N 也可以，但我不想放松太多。或者，引入一些简化约束也可以，比如：凸区域必须是三角形（只能用3个点来定义）。
我想有了三角形约束，我可以对输入点的随机样本进行强力搜索，搜索由 3 个点定义的所有可能的三角形，但这类似于 O(S^4)，其中S 是我的样本量。 S^3 个三角形和 O(S) 遍历点以检查它们是否在该三角形中。
如果 n 不是太大，您可以尝试整数规划。枚举所有n选4个点的4种组合，过滤掉其他三个x2, x3, x4形成的三角形内没有一个点x1的组合，写一个约束
-x1 + x2 + x3 + x4 <= 2
对于每个组合，加上一个基数约束
sum_i x_i = n
并最小化
sum_i penalty_i x_i.
有算法吗？如果它是一个近似值或者添加进一步的约束来简化也没关系。这里有更详细的说法
我在一些低维 space（比如 2d）中有 K 个点。每个人都有一个惩罚（可以是零）。如果有帮助，我们可以限制它，以便只有几个离散的惩罚值，而不是一个连续体。
给定 N，我想找到一个恰好包含 N 个这些点的凸区域。一个区域的代价是所有点的惩罚之和。我们希望将此成本降至最低。
例如，你必须找到一个恰好有 N 棵树的凸区域。有些树比其他树更差（更高的惩罚），所以你想找到最佳的这样的区域。
是否有已知的算法？如果解决方案只是近似最优也没关系。只覆盖大约 N 也可以，但我不想放松太多。或者，引入一些简化约束也可以，比如：凸区域必须是三角形（只能用3个点来定义）。
我想有了三角形约束，我可以对输入点的随机样本进行强力搜索，搜索由 3 个点定义的所有可能的三角形，但这类似于 O(S^4)，其中S 是我的样本量。 S^3 个三角形和 O(S) 遍历点以检查它们是否在该三角形中。
如果 n 不是太大，您可以尝试整数规划。枚举所有n选4个点的4种组合，过滤掉其他三个x2, x3, x4形成的三角形内没有一个点x1的组合，写一个约束
-x1 + x2 + x3 + x4 <= 2
对于每个组合，加上一个基数约束
sum_i x_i = n
并最小化
sum_i penalty_i x_i.