点集子集的最小周长凸包

给定平面上的 n 个点。没有 3 个共线。

给定数字 k。

找到 k 个点的子集，使得 k 个点的凸包在 k 个点的子集的任何凸包中具有最小周长。

我可以想到一个简单的方法，运行时间为 O(n^k k log k)。 （找到大小为 k 的每个子集的凸包并输出最小值）。

我认为这是一个NP问题，但我找不到任何适合还原的东西。

有人对这个问题有想法吗？

一个例子，

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

Result:

{(0,0),(0,1),(1,0)}

由于该集合包含 3 个点，因此结果的凸包和周长小于任何其他 3 点集合的结果。

这可以在 O(kn^3) 时间和 O(kn^2) 空间内完成（如果您想要实际点，则可能是 O(kn^3) ）。

这张纸：http://www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf http://www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf

Eppstein 等人提出的算法可以解决最小周长和其他权重函数（如面积、内角总和等）的问题，这些函数遵循一定的约束，即使标题说的是最小面积（周长请参见推论 5.3）。

基本思想是如下的动态规划方法（阅读第 4 节的前几段）：

假设 S 是给定的点集，Q 是 k 个点的具有最小周长的凸包。

令 p1 为 Q 的最底点，p2 和 p3 为船体上按逆时针顺序排列的下一个点。

我们可以将 Q 分解为三角形 p1p2p3 和 k-1 个点 Q' 的凸包（与三角形 p1p2p3 共享边 p1p3）。

主要观察结果是 Q' 是 k-1 的最优值，其中最底点是 p1，下一个点是 p3，并且 Q' 的所有点都位于线 p2->p3 的同一侧。

因此，为每个四元组 (pi, pj, pk, m) 维护一个最佳多边形的 4d 数组，使得

• 该多边形是 S 的 m 个点的凸包。
• pi 是多边形的最底点。
• pj 是逆时针顺序的下一个顶点，
• 多边形的所有点都位于 pi -> pj 线的左侧。
• 所有点都与 pi 位于 pj->pk 的同一侧。

给定 m

该论文准确地描述了如何做到这一点以实现规定的空间和时间限制。

希望有帮助。