尽可能小的区域以覆盖一定百分比的点

Question

给定一组2D点，我想定义一个多边形，覆盖一定百分比的所有点，同时保持它的面积尽可能小。

我开始想到这样一个算法：

1. 从最接近平均值的2点开始
2. 在所有其他点上循环
3. 添加导致覆盖面积最小的点
4. 重复2和3直到达到所需的百分比

我想这会起作用，但听起来效率很低。我对计算面积的最佳选择是使用凸包的现有实现。我的问题听起来也像一个经典的数学问题，我怀疑有一个scipy函数可能会开箱即用。

什么是解决或近似这个问题的有效而简单的方法？

编辑：生成的多边形应该是凸的

Answer 1

1. 找到所有点的中心。
2. 将所有点移到原点。
3. 切换到极坐标。
4. 按极性中心半径增加的顺序对点进行排序。
5. 选择最接近原点的x%。
6. 生成围绕这些点的凸包。

不确定它是否是最优的，但它似乎可以计算，至少应该是一个很好的近似值。