algorithm - 给定二维空间中的一组点，每个点都有一些惩罚，找到一个正好覆盖 N 个点的凸区域，最小化惩罚

有这个算法吗？如果它是一个近似值或添加进一步的约束以简化它是可以的。这是更详细的声明

我在一些低维空间（比如 2d）中有 K 个点。每个都有一个惩罚（可能是零）。如果它有帮助，我们可以限制它，以便只有几个离散的惩罚值，而不是一个连续体。

给定 N，我想找到一个恰好包含 N 个这些点的凸区域。一个区域的成本是所有点的惩罚的总和。我们希望将这个成本降到最低。

例如，您必须找到恰好有 N 棵树的凸面区域。有些树比其他树更差（更高的惩罚），所以你想找到最优的这样的区域。

有一个已知的算法吗？如果解决方案只是近似最优，那也没关系。只覆盖大约 N 也是可以的，但我不想放松太多。或者，可以引入一些简化约束，例如：凸区域必须是三角形（只能由3个点定义）。

我想通过三角形约束，我可以对输入点的随机样本进行强力搜索，搜索由 3 个点定义的所有可能的三角形，但这类似于 O(S^4)，其中 S 是我的样本大小. S^3 个三角形和 O(S) 循环遍历点以检查它们是否在该三角形中。

标签： algorithmgeometryconvex-hullapproximation

如果 n 不是太大，您可以尝试整数编程。x1枚举所有n个选择4个点的4个组合，过滤掉其他三个组成的三角形内没有一个点的组合x2, x3, x4，写一个约束

-x1 + x2 + x3 + x4 <= 2

对于每个组合，加上一个基数约束

sum_i x_i = n

并最小化

sum_i penalty_i x_i.